微信网站的好处,o2o交易平台有哪些,贵阳建站模板,wordpress 获取文章链接多维动态规划 机器人路径问题思路代码实现 最小路径和问题动态规划思路状态转移方程边界条件 代码实现 最长回文子串思路代码实现 最长公共子序列#xff08;LCS#xff09;题目描述解决方案 —— 动态规划1. 状态定义2. 状态转移方程3. 初始化4. 代码实现 编辑距离#xff… 多维动态规划 机器人路径问题思路代码实现 最小路径和问题动态规划思路状态转移方程边界条件 代码实现 最长回文子串思路代码实现 最长公共子序列LCS题目描述解决方案 —— 动态规划1. 状态定义2. 状态转移方程3. 初始化4. 代码实现 编辑距离Edit Distance题目描述解法动态规划状态转移方程边界条件 代码实现 二维动态规划答题总结1. 识别动态规划问题2. 解决二维 DP 题目的通用步骤Step 1: 定义 DP 数组Step 2: 确定状态转移方程Step 3: 初始化边界条件Step 4: 计算 DP 数Step 5: 优化空间复杂度 3. 典型题目总结 机器人路径问题
给定一个 ( m × n ) ( m \times n ) (m×n) 的网格机器人位于左上角起始点 “Start”只能向下或者向右移动一步目标是到达右下角终点 “Finish”。求总共有多少条不同的路径 思路 状态定义 用二维数组 dp[i][j] 表示到达网格中位置 ( i , j ) (i, j) (i,j) 的不同路径数。 状态转移 由于机器人只能从上方或左侧移动到 ( i , j ) (i, j) (i,j) [ d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i ] [ j − 1 ] ] [ dp[i][j] dp[i-1][j] dp[i][j-1] ] [dp[i][j]dp[i−1][j]dp[i][j−1]] 初始化 起点dp[0][0] 1。第一行 ( i 0 ) (i 0) (i0)上的所有位置只能从左边到达因此路径数均为 1。第一列 ( j 0 ) (j 0) (j0)上的所有位置只能从上面到达因此路径数均为 1。 答案 最终答案为 dp[m-1][n-1]。
代码实现
class Solution {public int uniquePaths(int m, int n) {// 创建一个 m x n 的二维数组 dp用于记录每个位置的路径数int[][] dp new int[m][n];// 初始化第一列每个位置只有一种路径一直向下走for (int i 0; i m; i) {dp[i][0] 1;}// 初始化第一行每个位置只有一种路径一直向右走for (int j 0; j n; j) {dp[0][j] 1;}// 计算其他位置的路径数for (int i 1; i m; i) {for (int j 1; j n; j) {// 当前格子的路径数等于上方格子和左侧格子的路径数之和dp[i][j] dp[i - 1][j] dp[i][j - 1];}}// 返回右下角的路径数return dp[m - 1][n - 1];}
}最小路径和问题
给定一个包含非负整数的 ( m × n ) ( m \times n ) (m×n) 网格 grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。 动态规划思路
我们可以使用动态规划来解决这个问题定义状态 dp[i][j] 表示从起点 ((0, 0)) 到达位置 ((i, j)) 的最小路径和。
状态转移方程
对于位置 ( i , j ) (i, j) (i,j)由于只能从上方 ( i − 1 , j ) (i-1, j) (i−1,j) 或左侧 ( i , j − 1 ) (i, j-1) (i,j−1) 移动过来因此有 d p [ i ] [ j ] g r i d [ i ] [ j ] min ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] grid[i][j] \min(dp[i-1][j],\ dp[i][j-1]) dp[i][j]grid[i][j]min(dp[i−1][j], dp[i][j−1])
边界条件
起点 d p [ 0 ] [ 0 ] g r i d [ 0 ] [ 0 ] dp[0][0] grid[0][0] dp[0][0]grid[0][0]第一行 只能从左侧移动所以 d p [ 0 ] [ j ] d p [ 0 ] [ j − 1 ] g r i d [ 0 ] [ j ] (对于 j ≥ 1 ) dp[0][j] dp[0][j-1] grid[0][j] \quad \text{(对于 } j \ge 1\text{)} dp[0][j]dp[0][j−1]grid[0][j](对于 j≥1)第一列 只能从上面移动所以 d p [ i ] [ 0 ] d p [ i − 1 ] [ 0 ] g r i d [ i ] [ 0 ] (对于 i ≥ 1 ) dp[i][0] dp[i-1][0] grid[i][0] \quad \text{(对于 } i \ge 1\text{)} dp[i][0]dp[i−1][0]grid[i][0](对于 i≥1) 代码实现
下面是基于上述思路的 Java 代码实现
class Solution {public int minPathSum(int[][] grid) {int m grid.length;int n grid[0].length;// 创建 dp 数组dp[i][j] 表示到达 (i, j) 的最小路径和int[][] dp new int[m][n];// 初始化起点dp[0][0] grid[0][0];// 初始化第一行for (int j 1; j n; j) {dp[0][j] dp[0][j - 1] grid[0][j];}// 初始化第一列for (int i 1; i m; i) {dp[i][0] dp[i - 1][0] grid[i][0];}// 填充 dp 数组的剩余部分for (int i 1; i m; i) {for (int j 1; j n; j) {dp[i][j] grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]);}}// 返回右下角的最小路径和return dp[m - 1][n - 1];}
}最长回文子串
给定一个字符串 s找出 s 中最长的回文子串。 思路
我们可以利用动态规划来解决该问题。设 dp[i][j] 表示子串 s[i...j] 是否为回文。状态转移方程为 d p [ i ] [ j ] ( s [ i ] s [ j ] ) ( j − i 3 或 d p [ i 1 ] [ j − 1 ] ) dp[i][j] (s[i] s[j]) \, \\ \, (j - i 3 \text{ 或 } dp[i1][j-1]) dp[i][j](s[i]s[j])(j−i3 或 dp[i1][j−1])
具体说明如下
当 s[i] 和 s[j] 不相等时s[i...j] 不是回文故 dp[i][j] false。当 s[i] 和 s[j] 相等时 如果子串长度小于等于 3即 j - i 3那么 s[i...j] 一定是回文因为此时中间最多只有一个字符。如果子串长度大于 3则需依赖子串 s[i1...j-1] 是否为回文即 dp[i1][j-1]。
在更新过程中我们记录当前最长回文子串的起始位置和长度最终返回最长的回文子串。 代码实现
class Solution {public String longestPalindrome(String s) {int n s.length();if (n 2) return s; // 如果字符串长度小于 2直接返回 s// dp[i][j] 表示 s[i...j] 是否为回文子串boolean[][] dp new boolean[n][n];int maxLen 1; // 记录最长回文子串的长度int start 0; // 记录最长回文子串的起始位置// 所有单个字符都是回文子串for (int i 0; i n; i) {dp[i][i] true;}// 枚举子串的结束位置 j从 1 到 n-1for (int j 1; j n; j) {// 枚举子串的起始位置 i从 0 到 j-1for (int i 0; i j; i) {if (s.charAt(i) s.charAt(j)) {// 如果子串长度小于等于 3则必为回文否则看内部子串是否为回文if (j - i 3) {dp[i][j] true;} else {dp[i][j] dp[i 1][j - 1];}} else {dp[i][j] false;}// 如果 dp[i][j] 为 true 且子串长度大于当前记录的最长长度则更新结果if (dp[i][j] j - i 1 maxLen) {maxLen j - i 1;start i;}}}return s.substring(start, start maxLen);}
}最长公共子序列LCS
题目描述
给定两个字符串 text1 和 text2返回它们的 最长公共子序列LCS的长度。如果不存在公共子序列则返回 0。
定义
子序列从字符串中删除某些字符也可以不删除但不改变字符的相对顺序后形成的新字符串。公共子序列同时属于 text1 和 text2 的子序列。 解决方案 —— 动态规划
1. 状态定义
设 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。
2. 状态转移方程
若 text1[i-1] text2[j-1]即当前字符相同 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] 1 dp[i][j] dp[i-1][j-1] 1 dp[i][j]dp[i−1][j−1]1若 text1[i-1] ! text2[j-1]即当前字符不同 d p [ i ] [ j ] max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] \max(dp[i-1][j], dp[i][j-1]) dp[i][j]max(dp[i−1][j],dp[i][j−1]) 取两种删除策略的最大值 dp[i-1][j]删除 text1 的当前字符dp[i][j-1]删除 text2 的当前字符
3. 初始化
dp[0][j] 0空字符串 text1 和 text2 的最长公共子序列长度为 0dp[i][0] 0同理
4. 代码实现
class Solution {public int longestCommonSubsequence(String text1, String text2) {int m text1.length(), n text2.length();int[][] dp new int[m 1][n 1];for (int i 1; i m; i) {for (int j 1; j n; j) {if (text1.charAt(i - 1) text2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}
}dp 数组大小是 (m1) × (n1)是为了处理空字符串避免 dp[i-1][j-1] 边界问题。 这样可以统一状态转移方程减少边界检查提高代码的可读性和稳定性。
编辑距离Edit Distance
题目描述
给定两个单词 word1 和 word2请返回将 word1 转换成 word2 所使用的最少操作数。
可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符 解法动态规划
我们定义 dp[i][j] 为 将 word1[0:i] 转换为 word2[0:j] 所需的最少操作数。
状态转移方程 如果 word1[i-1] word2[j-1]即当前字符相同则不需要额外操作 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] dp[i][j] dp[i-1][j-1] dp[i][j]dp[i−1][j−1] 如果 word1[i-1] ≠ word2[j-1]即当前字符不同可以执行三种操作 插入字符dp[i][j-1] 1相当于在 word1 插入 word2[j-1]这样 word1[0:i] 变成 word2[0:j]。删除字符dp[i-1][j] 1相当于删除 word1[i-1]这样 word1[0:i-1] 变成 word2[0:j]。替换字符dp[i-1][j-1] 1将 word1[i-1] 变成 word2[j-1]这样 word1[0:i] 变成 word2[0:j]。 取三者最小值 d p [ i ] [ j ] min ( d p [ i − 1 ] [ j − 1 ] 1 , d p [ i ] [ j − 1 ] 1 , d p [ i − 1 ] [ j ] 1 ) dp[i][j] \min(dp[i-1][j-1] 1, \quad dp[i][j-1] 1, \quad dp[i-1][j] 1) dp[i][j]min(dp[i−1][j−1]1,dp[i][j−1]1,dp[i−1][j]1)
边界条件
dp[0][j] jword1 为空需要插入 j 个字符dp[i][0] iword2 为空需要删除 i 个字符 代码实现
class Solution {public int minDistance(String word1, String word2) {int m word1.length(), n word2.length();int[][] dp new int[m 1][n 1];// 初始化边界条件for (int i 0; i m; i) dp[i][0] i;for (int j 0; j n; j) dp[0][j] j;// 计算 dp 数组for (int i 1; i m; i) {for (int j 1; j n; j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1]; // 无需操作} else {dp[i][j] Math.min(dp[i - 1][j - 1], // 替换Math.min(dp[i - 1][j], // 删除dp[i][j - 1])) 1; // 插入}}}return dp[m][n];}
}二维动态规划答题总结
1. 识别动态规划问题
当问题具有以下特征时可以考虑使用动态规划Dynamic Programming, DP
最优子结构Optimal Substructure问题可以拆解成子问题且子问题的最优解可以构成原问题的最优解。重叠子问题Overlapping Subproblems子问题在递归求解过程中被多次计算。状态转移State Transition能够从小规模问题推导出大规模问题的解。
对于 二维动态规划通常涉及两个字符串或两个维度的数据例如
子序列问题如最长公共子序列 LCS子数组/子矩阵问题如最小路径和、最大乘积子数组字符串编辑问题如编辑距离 2. 解决二维 DP 题目的通用步骤
Step 1: 定义 DP 数组
确定 dp[i][j] 的含义一般是
字符串匹配问题dp[i][j] 代表 text1[0:i] 和 text2[0:j] 的匹配结果如最长公共子序列。路径问题dp[i][j] 代表到达 grid[i][j] 的最优解如最短路径。编辑距离dp[i][j] 代表 word1[0:i] 变成 word2[0:j] 的最少操作次数。 Step 2: 确定状态转移方程
一般来说状态转移方程由以下情况组成
字符匹配时的继承状态如 dp[i][j] dp[i-1][j-1]最长公共子序列。考虑不同操作的最优值 取最小值如 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1。取最大值如 max(dp[i-1][j], dp[i][j-1])。取累积值如 dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])。 Step 3: 初始化边界条件
不同问题的边界初始化方式不同常见情况
子序列问题 dp[i][0] 0因为空串与任何串的 LCS 都是 0。dp[0][j] 0因为空串与任何串的 LCS 都是 0。 路径问题 dp[0][j] 为前缀和只能从左走。dp[i][0] 为前缀和只能从上走。 编辑距离问题 dp[i][0] i表示 word1 变成空串需要 i 次删除。dp[0][j] j表示空串变成 word2 需要 j 次插入。 Step 4: 计算 DP 数
通过 两层循环 计算 dp[i][j]通常是 O(m × n)。先遍历 行 或 列依赖于状态转移方程。 Step 5: 优化空间复杂度
通常二维 DP 使用 O(m × n) 的空间可以优化至 O(n) 甚至 O(1)
滚动数组用两个数组 prev 和 curr 代替整个 dp 矩阵适用于 LCS、编辑距离。原地修改如果问题允许我们可以在原数组上修改适用于路径问题。 3. 典型题目总结
题目状态定义状态转移方程时间复杂度空间优化最长公共子序列LCSdp[i][j] 代表 text1[0:i] 和 text2[0:j] 的 LCS 长度dp[i][j] dp[i-1][j-1] 1匹配或 max(dp[i-1][j], dp[i][j-1])O(m × n)O(n)编辑距离Edit Distancedp[i][j] 代表 word1[0:i] 变成 word2[0:j] 的最少操作次数dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1O(m × n)O(n)最小路径和dp[i][j] 代表到达 grid[i][j] 的最小路径和dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])O(m × n)O(n)最长回文子串中心扩展或 DPdp[i][j] 代表 s[i:j] 是否是回文dp[i][j] (s[i] s[j] dp[i1][j-1])O(n²)O(n²) → O(1)
