LC 狂刷 66 道 Dynamic-Programming 算法题。跟动态规划说拜拜
// 给出初始值 dp[0] = 0;dp[1] = 1;// 通过关系式来计算出 dp[n]for(int i = 2; i <= n; i++){dp[i] = dp[i-1] + dp[i-2];}// 把最终结果返回 return dp[n];}
（4）、再说初始化
大家先想以下，你觉得，上面的代码有没有问题？
答是有问题的，还是错的，错在对初始值的寻找不够严谨，这也是我故意这样弄的，意在告诉你们，关于初始值的严谨性。例如对于上面的题，当 n = 2 时，dp[2] = dp[1] + dp[0] = 1。这显然是错误的，你可以模拟一下，应该是 dp[2] = 2。
也就是说，在寻找初始值的时候，一定要注意不要找漏了，dp[2] 也算是一个初始值，不能通过公式计算得出。有人可能会说，我想不到怎么办？这个很好办，多做几道题就可以了。
下面我再列举三道不同的例题，并且，再在未来的文章中，我也会持续按照这个步骤，给大家找几道有难度且类型不同的题。下面这几道例题，不会讲的特性详细哈。实际上 ，上面的一维数组是可以把空间优化成更小的，不过我们现在先不讲优化的事，下面的题也是，不讲优化版本。
案例二：二维数组的 DP
我做了几十道 DP 的算法题，可以说，80% 的题，都是要用二维数组的，所以下面的题主要以二维数组为主，当然有人可能会说，要用一维还是二维，我怎么知道？这个问题不大，接着往下看。
问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
还是老样子，三个步骤来解决。
步骤一、定义数组元素的含义
由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。那么，dp[m-1] [n-1] 就是我们要的答案了。
注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以 右下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要找的答案。
步骤二：找出关系数组元素间的关系式
想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达
因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。
步骤三、找出初始值
显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下：
dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往左走
dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走
撸代码
三个步骤都写出来了，直接看代码
public static int uniquePaths(int m, int n) {if (m <= 0 || n <= 0) {return 0;}
int[][] dp = new int[m][n]; //// 初始化 for(int i = 0; i < m; i++){dp[i][0] = 1;}for(int i = 0; i < n; i++){dp[0][i] = 1;}// 推导出 dp[m-1][n-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];}
案例三、二维数组 DP
写到这里，有点累了，，但还是得写下去，所以看的小伙伴，你们可得继续看呀。下面这道题也不难，比上面的难一丢丢，不过也是非常类似
问题描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
举例：输入:arr = [[1,3,1],[1,5,1],[4,2,1]]输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
和上面的差不多，不过是算最优路径和，
步骤一、定义数组元素的含义
由于我们的目的是从左上角到右下角，最小路径和是多少，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，最下的路径和是 dp[i] [j]。那么，dp[m-1] [n-1] 就是我们要的答案了。
注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以 由下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要走的答案。
步骤二：找出关系数组元素间的关系式
想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达
不过这次不是计算所有可能路径，而是计算哪一个路径和是最小的，那么我们要从这两种方式中，选择一种，使得 dp[i] [j] 的值是最小的，显然有dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格种的值步骤三、找出初始值
显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下：
dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行，机器人只能一直往左走
dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列，机器人只能一直往下走代码如下
public static int uniquePaths(int[][] arr) {int m = arr.length;int n = arr[0].length;if (m <= 0 || n <= 0) {return 0;}
int[][] dp = new int[m][n]; //// 初始化 dp[0][0] = arr[0][0];// 初始化最左边的列 for(int i = 1; i < m; i++){dp[i][0] = dp[i-1][0] + arr[i][0];}// 初始化最上边的行 for(int i = 1; i < n; i++){dp[0][i] = dp[0][i-1] + arr[0][i];}// 推导出 dp[m-1][n-1]for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];}}return dp[m-1][n-1];}
案例 4：编辑距离
这次给的这道题比上面的难一些，在 leetcdoe 的定位是 hard 级别。
问题描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符删除一个字符替换一个字符
示例 1:输入: word1 = "horse", word2 = "ros"输出: 3 解释:horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')
解答
还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决，并且 90%是采用二维数组。
步骤一、定义数组元素的含义
由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为：当字符串 word
1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。
还未添加个人签名 2021.10.31 加入
还未添加个人简介
评论