于是按照这个公式不停着填充到最后一行，结果如下：
最后 dp[n-1] 就是我们要求的结果了。所以优化之后，代码如下： public static int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) { return 0; } int[] dp = new int[n]; // // 初始化 for(int i = 0; i < n; i++){ dp[i] = 1; } // 公式：dp[i] = dp[i-1] + dp[i] for (int i = 1; i < m; i++) { // 第 i 行第 0 列的初始值 dp[0] = 1; for (int j = 1; j < n; j++) { dp[j] = dp[j-1] + dp[j]; } } return dp[n-1]; } 案例2：编辑距离
接着我们来看昨天的另外一道题，就是编辑矩阵，这道题的优化和这一道有一点点的不同，上面这道 dp[i][j] 依赖于 dp[i-1][j] 和 dp[i][j-1]。而还有一种情况就是 dp[i][j] 依赖于 dp[i-1][j]，dp[i-1][j-1] 和 dp[i][j-1]。
问题描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
解答
昨天的代码如下所示，不懂的记得看之前的文章哈：告别动态规划，连刷40道动规算法题，我总结了动规的套路
public int minDistance(String word1, String word2) { int n1 = word1.length(); int n2 = word2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; // dp[0][0...n2]的初始值 for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1; // dp[0...n1][0] 的初始值 for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1; // 通过公式推出 dp[n1][n2] for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1 if (word1.charAt(i - 1) == word2.charAt(j - 1)){ p[i][j] = dp[i - 1][j - 1]; }else { dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1; } } } return dp[n1][n2]; }没有优化之间的空间复杂度为 O(n*m)
大家可以自己动手做下，按照上面的那个模式，你会优化吗？
对于这道题其实也是一样的，如果要计算 第 i 行的值，我们最多只依赖第 i-1 行的值，不需要用到第 i-2 行及其以前的值，所以一样可以采用一维 dp 来处理的。
不过这个时候要注意，在上面的例子中，我们每次更新完 (i, j) 的值之后，就会把 (i, j-1) 的值抛弃，也就是说之前是一边更新 dp[i] 的值，一边把 dp[i] 的旧值抛弃的，不过在这道题中则不可以，因为我们还需要用到它。
哎呀，直接举例子看图吧，文字绕来绕去估计会绕晕你们。当我们要计算图中 (i,j) 的值的时候，在案例1 中，我们值需要用到 (i-1, j) 和 (i, j-1)。（看图中方格的颜色）
不过这道题中，我们还需要用到 （i-1, j-1) 这个值（但是这个值在以往的案例1 中，它会被抛弃掉）
所以呢，对于这道题，我们还需要一个额外的变量 pre 来时刻保存 (i-1,j-1) 的值。推导公式就可以从二维的 dp[i][j] = min(dp[i-1][j] , dp[i-1][j-1] , dp[i][j-1]) + 1
转化为一维的
dp[i] = min(dp[i-1], pre, dp[i]) + 1。