算法四-8月11-动态规划合集

hahg大约 32 分钟

算法四-8月11-动态规划合集

二十八、组合总和

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484952&idx=1&sn=a268b086be9425bb56598d8cdf1996aa&chksm=fd9cad07caeb241173c9d524f9230a8fe4efa9d215a0ec1756152ed452b0a611c13ef7e14bba&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「39. 组合总和」**，难度为 Medium。
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：[ [7], [2,2,3] ]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

（1）DFS+回溯

如何快速判断一道题是否应该使用 DFS + 回溯算法来爆搜。
总的来说，你可以从两个方面来考虑：
「1. 求的是所有的方案，而不是方案数。」 由于求的是所有方案，不可能有什么特别的优化，我们只能进行枚举。这时候可能的解法有动态规划、记忆化搜索、DFS + 回溯算法。
「2. 通常数据范围不会太大，只有几十。」 如果是动态规划或是记忆化搜索的题的话，由于它们的特点在于低重复/不重复枚举，所以一般数据范围可以出到 10⁵ ~ 10⁷，而 DFS + 回溯的话，通常会限制在 30 以内。
这道题数据范围是 30 以内，而且是求所有方案。因此我们使用 DFS + 回溯来求解：

动态规划的路线就相当于求出所有方案，所以当看到求出所有方案，而不是方案数，就可以考虑用动态规划。这道题目比较像背包问题，每次选择一个数，目标数减少，然后继续选择。

由于是无限制选择相同的数字：

可以选择一个数字后进入下一个递归
或者选择多个相同的数字后再进入下一个递归，下面代码为这种解法。
下面代码有点与众不同：

先压栈再添加到当前结果集，所以会从原数组的最后一个数添加
遍历当前数字的使用次数后，需要撤销所遍历的数字。
1. 遍历使用次数的代码第 28 行—— for (int i = 0; cs[u] * i <= t; i++) 代表在到达 target 之前，不断增加当前数字的次数
2. 撤销所遍历的数字需要移除一样的次数，所以循环的条件一样，如第 36 行

class Solution {
  public List<List<Integer>> combinationSum(int[] cs, int t) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> cur = new ArrayList<>();
    dfs(cs, t, 0, ans, cur);
    return ans;
  }

  /**
     * cs: 原数组，从该数组进行选数
     * t: 还剩多少值需要凑成。起始值为 target ，代表还没选择任何数；当 t = 0，代表选择的数凑成了 target
     * u: 当前决策到 cs[] 中的第几位
     * ans: 最终结果集
     * cur: 当前结果集
     */
  void dfs(int[] cs, int t, int u, List<List<Integer>> ans, List<Integer> cur) {
    // 如果target为0则添加到结果里并返回
    if (t == 0) {
      ans.add(new ArrayList<>(cur));
      return;
    }
    
    // 如果选择的数字为最后一个或者target小于0则返回上一个递归
    // 因为没有排序，所以当选择的数字为最后一个，target大于0的情况存在
    if (u == cs.length || t < 0) return;

    // 枚举 cs[u] 的使用次数，使用零次、一次以及多次
    for (int i = 0; cs[u] * i <= t; i++) {
      dfs(cs, t - cs[u] * i, u + 1, ans, cur);
      // 由于每次
      cur.add(cs[u]);
    }
    
    // 进行回溯，将之前添加去掉。
    // 注意回溯总是将数组的最后一位弹出
    for (int i = 0; cs[u] * i <= t; i++) {
      cur.remove(cur.size() - 1);
    }
  }
}

时间复杂度：由于每个数字的使用次数不确定，因此无法分析具体的复杂度。但是 DFS 回溯算法通常是指数级别的复杂度（因此数据范围通常为 30 以内）。这里暂定 $O ( n \times 2 ^{n} )$
空间复杂度：同上。复杂度为 $O ( n \times 2 ^{n} )$

二十九、组合总和2

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484964&idx=1&sn=9ab54e6eaf9b0298724a1be8e507f62d&chksm=fd9cad3bcaeb242d8390a2c4196c0811d1520c13ea7f7eb705bdfbe9deb67d60d7655ac50c87&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「40. 组合总和 II」**，难度为 Medium。
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8
所求解集为:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

（1）DFS+回溯

该题目与上一道题很类似，但这道题要求每个数字只能用一次。可以按照模板来解决问题，但也可以 使用每个数字只能用一次 的特点，每个数字只有两种状态，选择或者不选择，所以就不需要循环来确定第 n 个数是哪个数字了。即不用确定答案的第 1 个数是数组中第 1 个数还是第 2 个数、答案的第 2 个数是第 3 个数还是第 n 个数。

只用将每一个数字的两个状态 全部组合一次，再看是否符合要求。注意要去重，所以要【排序 + Set集合】。

需要去重证明：假设 candidates = [1, 1, 1, 1, 3]，target = 5。答案会得到多个 [1, 1, 3]，因为有在 4 个数字中，取其中两个，可以取到 6 种不同的结果。下标分别为 [ [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3] ]

核心代码：每层递归都会调用两个下层递归，第 5 行和第 11 行，分别代表该层的数字是否使用

// 使用 cs[u]
cur.add(cs[u]);

// 进行递归
dfs(cs, t - cs[u], u + 1, ans, cur);

// 进行回溯
cur.remove(cur.size() - 1);

// 不使用 cs[u]
dfs(cs, t, u + 1, ans, cur);

（2）全部代码

class Solution {
  public List<List<Integer>> combinationSum2(int[] cs, int t) {
    Arrays.sort(cs);
    Set<List<Integer>> ans = new HashSet<>();
    List<Integer> cur = new ArrayList<>();
    dfs(cs, t, 0, ans, cur);
    return new ArrayList<>(ans);
  }

  /**
     * cs: 原数组，从该数组进行选数
     * t: 还剩多少值需要凑成。起始值为 target ，代表还没选择任何数；当 t = 0，代表选择的数凑成了 target
     * u: 当前决策到 cs[] 中的第几位
     * ans: 最终结果集
     * cur: 当前结果集
     */
  void dfs(int[] cs, int t, int u, Set<List<Integer>> ans, List<Integer> cur) {
    if (t == 0) {
      ans.add(new ArrayList<>(cur));
      return;
    }
    if (u == cs.length || t < 0) return;

    // 使用 cs[u]
    cur.add(cs[u]);
    
    // 进行递归
    dfs(cs, t - cs[u], u + 1, ans, cur);

    // 进行回溯
    cur.remove(cur.size() - 1);
    
    // 不使用 cs[u]
    dfs(cs, t, u + 1, ans, cur);
  }
}

时间复杂度： DFS 回溯算法通常是指数级别的复杂度（因此数据范围通常为 30 以内）。这里暂定。这里暂定 $O ( n \times 2 ^{n} )$
空间复杂度：同上。复杂度为 $O ( n \times 2 ^{n} )$

三十、组合总和3

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484985&idx=1&sn=7b34d7445e98f5c4365714f93d3a3f52&chksm=fd9cad26caeb24304fff97709e7262c3bc569bde50c923ba8f878328fd2d034cbb564d2d1eaa&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「216. 组合总和 III」**，难度为 Medium。
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [ [1,2,4] ]
示例 2:
输入: k = 3, n = 9
输出: [ [1,2,6], [1,3,5], [2,3,4] ]

（1）DFS+回溯

这道题依然是不能使用重复的数字，所以就可以使用总和2 的方法，把每一个数的两种情况——取或不取都遍历一边，就能得出答案。

class Solution {
	// 为了减少递归的参数，设置了成员变量
  int n, k;
  public List<List<Integer>> combinationSum3(int _k, int _n) {
    n = _n;
    k = _k;

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> cur = new ArrayList<>();
    dfs(1, ans, cur, 0);
    return ans;
  }
  /**
     * u: 当前遍历到的数字
     * ans: 最终结果集
     * cur: 当前结果集
     * sum: 当前结果集的总和
     */
  void dfs(int u, List<List<Integer>> ans, List<Integer> cur, int sum) {
    // 如果总和和字符数量符合则添加到最终结果集中
    if (sum == n && cur.size() == k) {
      ans.add(new ArrayList<>(cur));
      return;
    }
    
    // 如果 遍历完1-9 或者 当前总和大于要求 或者 当前字符数量超过要求
    // 则返回，终止该层递归
    if (u == 10 || sum > n || cur.size() > k) return;
    
    // 使用数字 u
    cur.add(u);
    // 进行递归
    dfs(u + 1, ans, cur, sum + u);
    // 进行回溯
    cur.remove(cur.size() - 1);
    // 不使用数字 u
    dfs(u + 1, ans, cur, sum);
  }
}

（2）DFS模板归类

每一次独立的决策只对应 选择和不选 两种情况：

确定结束回溯过程的条件；
遍历每个位置，对每个位置进行决策（做选择 -> 递归 -> 撤销选择 -> 递归）

void dfs(当前位置, 路径(当前结果), 结果集) {
  if (当前位置 == 结束位置) {
    结果集.add(路径);
    return;
  }

  选择当前位置;    
  dfs(下一位置, 路径(当前结果), 结果集);
  撤销选择当前位置;
  dfs(下一位置, 路径(当前结果), 结果集);
}

每一次独立的决策都对应了多种选择（通常对应了每次决策能选择什么，或者每次决策能选择多少个 ...）。这个模板较万能，也能解决第 1 种模板的问题：

确定结束回溯过程的条件；
遍历所有的「选择」；
对选择进行决策 (做选择 -> 递归 -> 撤销选择)

void dfs(选择列表, 路径(当前结果), 结果集) {
    if (满足结束条件) {
        结果集.add(路径);
        return;
    }
        
    for (选择 in 选择列表) {
        做选择;
        dfs(路径’, 选择列表, 结果集);
        撤销选择;
    }
}

三十一、不同路径

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485037&idx=1&sn=d6d52c48600e655161e84f25d3402514&chksm=fd9cad72caeb2464e1d8adcd991ec178001472a6c6ddc02a1764bc74ea27a97f71fddbce9975&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「62. 不同路径」**，难度为 Medium。
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例1：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10⁹

（1）动态规划使用方法

1. 我们是如何确定本题可以使用动态规划来解决的？

通常我们要从**「有无后效性」**进行入手分析。

无后效性：如果对于某个状态，我们可以只关注状态的值，而不需要关注状态是如何转移过来的话，那么这就是一个无后效性的问题，可以考虑使用动态规划解决。
或者这样说：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响

另外一个更加实在的技巧，我们还可以通过 数据范围 来猜测是不是可以用 DP 来做。

因为 DP 是一个递推的过程，因此如果数据范围是 10⁵ ~ 10⁶的话，可以考虑是不是可以使用一维 DP 来解决；如果数据范围是 10² ~ 10³ 的话，可以考虑是不是可以使用二维 DP 来做 ...

2. 我们是如何确定本题的状态定义的？

说实话，DP 的状态定义很大程度是靠经验去猜的。

虽然大多数情况都是猜的，但也不是毫无规律，相当一部分题目的状态定义是与**「结尾」和「答案」**有所关联的。

3. 我们是如何确定状态转移方程的？

通常来说，如果我们的状态定义猜对了，「状态转移方程」就是对「最后一步的分情况讨论」。

如果我们有一个对的**「状态定义」的话，基本上「状态转移方程」**就是呼之欲出。

因此一定程度上，状态转移方程可以反过来验证我们状态定义猜得是否正确：

如果猜了一个状态定义，然后发现无法列出涵盖所有情况（不漏）的状态转移方程，多半就是状态定义猜错了，赶紧换个思路，而不是去死磕状态转移方程。

4. 对状态转移的要求是什么？

我们的状态转移是要做到**「不漏」还是「不重不漏」**取决于问题本身：

如果是求最值的话，我们只需要确保**「不漏」**即可，因为重复不影响结果。
如果是求方案数的话，我们需要确保**「不重不漏」**。

5. 我们是如何分析动态规划的时间复杂度的？

对于动态规划的复杂度/计算量分析，有多少个状态，复杂度/计算量就是多少。

因此一维 DP 的复杂度通常是线性的 O( n ) ，而二维 DP 的复杂度通常是平方的 O ( n² )

（2）解法

上面说的是动态规划的使用方法，其实在初学的时候都看的不太懂。所以可以简单来说：

当使用动态规划的时候，需要规划出状态转移。每一个值是怎么从之前的值转移过来的。

例如这道题，状态转移有三种情况：

当在第 1 行时：每一格都只能从左边走到当前格，所以只用看左一格的路径
当在第 1 列时：每一格都只能从上边走到当前格，所以只用看上一格的路径
当在中间区域时：每一个格可以从上边和左边走到当前格，所以要同时看上边和左边的路径

如果用代码表示：

定义 f[i][j] 为到达位置 (i,j) 的 不同路径数量。

那么 f[n-1][m-1] 就是我们最终的答案，而 f[0][0] = 1 是一个显而易见的起始条件。

当前位置只能 「往下」 移动，即有 f[i][j] = f[i - 1][j]
当前位置只能 「往右」 移动，即有 f[i][j] = f[i][j - 1]
当前位置即能 「往下」 也能 「往右」 移动，即有 f[i][j] = f[i][j - 1] + f[i - 1][j]（因为是路径数量所以上面的值和左边的值相加）

完整代码如下：

class Solution {
  public int uniquePaths(int m, int n) {
    int[][] f = new int[m][n];
    // 初始化第1格
    f[0][0] = 1;
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // 中间格
        if (i > 0 && j > 0) {
          f[i][j] = f[i - 1][j] + f[i][j - 1];
        } else if (i > 0) {
          // 第1列
          f[i][j] = f[i - 1][j];
        } else if (j > 0) {
          // 第1行
          f[i][j] = f[i][j - 1];
        }
      }
    }
    // 返回结果
    return f[m - 1][n - 1];
  }
}

时间复杂度： $O ( m \times n )$
空间复杂度： $O ( m \times n )$

三十二、不同路径 II

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485089&idx=1&sn=fd52fd088a5778c9ee101741d458605d&chksm=fd9cadbecaeb24a8f2115139f438fed36cddd96d00d5249d661684faf33b9874e62883720ae6&cur_album_id=1715134171561410565&scene=189#wechat_redirect

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
示例1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

（1）动态规划

这道题和上面的思路一致，不过状态转移需要增加新的情况：

当在第 1 行时：每一格都只能从左边走到当前格，所以只用看左一格的路径。
当在第 1 列时：每一格都只能从上边走到当前格，所以只用看上一格的路径
当在中间区域时：每一个格可以从上边和左边走到当前格，所以要同时看上边和左边的路径
如果当前格为障碍物时，则将当前格的路径数量设置为 0

第 4 点的添加，不会影响前面三点的运行，例如当第 1 行有一个障碍，障碍后面的所有格子都走不通。当路径数量设置为 0 后，这个 0 就会一直传递到后面的格。

完整代码：因为数组初始化会自动将所有格置为 0，所以代码中可以不用将障碍格设置为 0

class Solution {
  public int uniquePathsWithObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] f = new int[m][n];
    // 第1格可能也有障碍
    f[0][0] = grid[0][0] == 1 ? 0 : 1;
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // 如果当前格不是障碍
        if (grid[i][j] != 1) {
          if (i > 0 && j > 0) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
          } else if (i > 0) {
            f[i][j] = f[i - 1][j];
          } else if (j > 0) {
            f[i][j] = f[i][j - 1];
          }
        }
      }
    }
    return f[m - 1][n - 1];
  }
}

时间复杂度： $O ( m \times n )$
空间复杂度： $O ( m \times n )$

三十三、最小路径和

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485106&idx=1&sn=39adbde98707dc02a99e71f58cad5e7c&chksm=fd9cadadcaeb24bb2295d170f3de8dca0ce8e5acadccafbee82139dfe38ce1984435cd7a50ed&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「64. 最小路径和」**，难度为 Medium。
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例1：
输入：grid =
[ 
 [1, 3, 1],
 [1, 5, 1],
 [4, 2, 1] 
]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

（1）动态规划

根据题目，每次只能向下或者向右，所以状态转移有三种情况，和三十二道题一致：

当在第 1 行时：每一格都只能从左边走到当前格，所以只用看左一格的路径。
当在第 1 列时：每一格都只能从上边走到当前格，所以只用看上一格的路径。
当在中间区域时：每一个格可以从上边和左边走到当前格，所以要同时看上边和左边的路径

然后用代码实现的话，就有点不一样：

我们可以根据问题来调整我们的「状态定义」：定义 f[i][j] 为从 (0,0) 开始到达位置 (i,j) 的最小总和。
那么 f[m-1][n-1] 就是我们最终的答案，f[0][0] = grid[0][0] 是一个显而易见的起始状态。

当在第 1 行时，即有 f[i][j] = f[i-1][j] + grid[i][j]
当在第 1 列时，即有 f[i][j] = f[i][j-1] + grid[i][j]
当在中间区域时，即有 f[i][j] = min(f[i][j-1], f[i-1][j]) + grid[i][j]

完整代码如下：

class Solution {
  public int minPathSum(int[][] grid) {        
    int m = grid.length, n = grid[0].length;
    int[][] f = new int[m][n];
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // 初始化第1格
        if (i == 0 && j == 0) {
          f[i][j] = grid[i][j];
        } else {
          // 分别出第1行和第1列的情况
          int top  = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
          int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
          // 找出其中最小的一个值
          f[i][j] = Math.min(top, left);
        }
      }
    }
    return f[m - 1][n - 1];
  }
}

时间复杂度： $O ( m \times n )$
空间复杂度： $O ( m \times n )$

（2）输出路径

如果要输出总和最低的路径呢？（如果有多个答案，返回其中之一即可）

从原问题我们知道，我们需要从 (0,0) 一步步转移到 (m-1,n-1)。也就是我们需要扫描完整个方块（转移完所有的状态），才能得到答案。

那么显然，我们可以使用额外的数据结构来记录，我们是如何一步步转移到 f[m-1][n-1] 的，每一格都记录上一个格的位置。当整个 dp 过程结束后，我们再用另外的数据结构来回推并记录我们的路径。

记录上一个的位置有很多种方式：

存储的结构：
- 二维数组：便于存储，但占用比一维数组较大
- 一维数组：存储和取数不太方便，但占用少
记录的数据：
- 方向——中文记录：便于查看和理解，但 String 类型占用大
- 前一格的坐标：需要计算才能得知，但占用小

这里给出了【二维数组 + 方向】和【一位数组 + 前一格的坐标】的代码：

二维数组 + 方向：只需要在计算的过程中，额外添加一句记录的代码即可

for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) {
    if (i == 0 && j > 0) {
      f[i][j] = grid[i][j] + f[i][j - 1];
      // 记录方向
      g[i][j] = "左";
    } else if (j == 0 && i > 0) {
      f[i][j] = grid[i][j] + f[i - 1][j];
      // 记录方向
      g[i][j] = "上";
    } else if (i > 0 && j > 0) {
      int min = Integer.MAX_VALUE;
      if (f[i][j - 1] < f[i - 1][j]) {
        // 记录方向
        g[i][j] = "左";
        min = f[i][j - 1];
      }else {
        // 记录方向
        g[i][j] = "上";
        min = f[i - 1][j];
      }
      f[i][j] = grid[i][j] + min;
    }
  }
}

一位数组 + 前一格的坐标：需要额外的方法来 将二维数组的 x 和 y 转换成一维数组的下标 ，在输出时将一维数组中的下标转换为二维数组的 x 和 y

// 解析一维数组的下标
int[] parseIdx(int idx) {
  return new int[]{idx / n, idx % n};
}

// 转换为一维数组的下标
int getIdx(int x, int y) {
  return x * n + y;
}

然后再添加一句填充当前格的代码：

g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1);

记录完后需要反向记录路径。代码为一维数组的情况。

// 获取最终结果的下标
int idx = getIdx(m - 1, n - 1);
// 逆序将路径点添加到 path 数组中
// 行数代表路径下标，每行的第1列代表x，第2列代表y
int[][] path = new int[m + n][2];
// 初始化最后一格
path[m + n - 1] = new int[]{m - 1, n - 1};

// 填充pahth数组
for (int i = 1; i < m + n; i++) {
  path[m + n - 1 - i] = parseIdx(g[idx]);
  idx = g[idx];
}

// 顺序输出位置
for (int i = 1; i < m + n; i++) {
  int x = path[i][0], y = path[i][1];
  System.out.print("(" + x + "," + y + ") ");
}
System.out.println(" ");

（3）简化

既然求最终结果是正向，获取路径是反向。而我们可以将求最终结果进行 反向求解，这样就可以在求最终结果的同时获取路径。因为动态规划有最优子结构性质，无论是正向还是反向，都会符合使用动态规划的条件。

反向求解其实也很简单，就是把走的路反转就行了，原来【向右，向下】变成【向左，向上】

部分代码如下，与上面的代码相比，减少了反向获取路径的代码（输出语句一致，所以没有放上来）：

public int minPathSum(int[][] grid) {        
  m = grid.length;
  n = grid[0].length;
  int[][] f = new int[m][n];
  int[] g = new int[m * n];
  for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
      if (i == m - 1 && j == n - 1) {
        f[i][j] = grid[i][j];
      } else {
        int bottom = i + 1 < m ? f[i + 1][j] + grid[i][j] : Integer.MAX_VALUE;
        int right  = j + 1 < n ? f[i][j + 1] + grid[i][j] : Integer.MAX_VALUE; 
        f[i][j] = Math.min(bottom, right);
        g[getIdx(i, j)] = bottom < right ? getIdx(i + 1, j) : getIdx(i, j + 1);
      }
    }
  }
}

三十四、三角形最小路径和

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485123&idx=1&sn=8a427e56d472d1517b0983d8cdc5c629&chksm=fd9caddccaeb24caea7a272ddaf11d9bd476d4af710d0581c4b12223a11dd6edf33091006731&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「120. 三角形最小路径和」**，难度为 Medium。
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
				2
			3		4
		6 	5 	7
	4 	1 	8		3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
提示：
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
10^-4 <= triangle[i] [j] <= 10⁴
进阶：
你可以只使用 O( n ) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

（1）动态规划

这道题用常识来看状态转移，就是从当前格转移到其左边或右边，因为是个三角形。

但因为在代码中，使用的是数组来存储，就相当于从当前格转移到下一行的同列和下一列。就是将等腰三角形变成了直角三角形，例如下面所示。

这样一看，每一格的路径只需看是从正上还是左上来的，这就和上面几道路径题目差不多一样了。

完整代码如下：

第 12 ~ 17 行：简单几行，就将三种情况全部考虑到了
- 先对当前格的值与左上对比。因为第 13 行，所以 f[i][j] 是整型的最大值，与左上相比一定是左上最小，所以 f[i][j] == f[i - 1][j - 1] + val 。而执行这条语句的条件是，当前格不在第一列。
- 然后再将 f[i][j] 与正上对比。这样左上就可以与正上比大小。而执行这条语句的条件是，当前格不在最后一列。
- 如果在第一列时：左上的值没有赋值到 f[i][j] 里，所以 f[i][j] 等于整型的最大值，与正上对比时，就直接将正上赋值 f[i][j]
- 如果在最后一列：左上赋值到了 f[i][j] 里，而没有与正上比较，所以这时 f[i][j] 就等于左上。

class Solution {
  public int minimumTotal(List<List<Integer>> tri) {
    int n = tri.size();
    int ans = Integer.MAX_VALUE;
    int[][] f = new int[n][n];
    // 初始化第1格
    f[0][0] = tri.get(0).get(0);
    
    // i=2，代表从第2行开始即可
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i + 1; j++) {
        int val = tri.get(i).get(j);
        f[i][j] = Integer.MAX_VALUE;
        // 先将当前格与左上对比
        if (j != 0) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + val);
        // 然后再用当前格与正上对比
        if (j != i) f[i][j] = Math.min(f[i][j], f[i - 1][j] + val);
      }
    }
    // 在最后1行找出最小的值
    for (int i = 0; i < n; i++) ans = Math.min(ans, f[n - 1][i]);
    return ans;
  }
}

时间复杂度： $O ( n^{2} )$
空间复杂度： $O ( n^{2} )$

（2）进阶

从我们递推过程可以发现，在求第 i 行的状态时只依赖于第 i-1 行的状态。那么我们不需要存储所有行的状态值，可以对空间进行优化。

我们将使用滚动数组的方式。将列下标 f[i] 改成 f[i&1] 或者 f[i%2] 。
- 第 i - 1 行存在第 1 行，第 i 行的值存在第 2 行。
- 然后变成，第 i - 1 行存在第 2 行，第 i 行存在第 1 行。
- 所以每一次存的地方都要变换位置，行下标从 0 变成 1，从 1 变成 0，将下标与运算 1，或者对2 取余，都可以进行变换

完整代码如下：

public int minimumTotal(List<List<Integer>> tri) {
  int n = tri.size();
  int ans = Integer.MAX_VALUE;
  int[][] f = new int[2][n];
  f[0][0] = tri.get(0).get(0);
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i + 1; j++) {
      int val = tri.get(i).get(j);
      f[i & 1][j] = Integer.MAX_VALUE;
      if (j != 0) f[i & 1][j] = Math.min(f[i & 1][j], f[(i - 1) & 1][j - 1] + val);
      if (j != i) f[i & 1][j] = Math.min(f[i & 1][j], f[(i - 1) & 1][j] + val);
    }
  }
  for (int i = 0; i < n; i++) ans = Math.min(ans, f[(n - 1) & 1][i]);
  return ans;
}

时间复杂度： $O ( n^{2} )$
空间复杂度： $O ( n )$

事实上，这道题的空间还可以优化到 $O ( 1 )$ ：利用输入数据的空间进行状态转移。但频繁地操作 List ，会导致时间效率降低。在力扣的运行环境下，上面两个操作数组的算法运行时间大概 4 ms，而操作 List 的算法运行时间高达 8ms。

结合时间和空间来说，滚动数组的方式最好。

三十五、下降路径最小和

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485163&idx=1&sn=ffe456777bcda52c036e6eb2181d1932&chksm=fd9cadf4caeb24e21a57ce47295a54ee9d591dfbb857549a57c145cdeeabf8c4324b007fc18b&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的 「931. 下降路径最小和」，难度为 Medium。
给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的**「下降路径」的「最小和」**。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
具体来说，位置 (row,col) 的下一个元素应当是 (row+1,col-1)、(row+1,col) 或者 (row+1,col+1)
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗标注：
[[2, 1, 3], [[2, 1, 3],
[6, 5, 4], [6, 5, 4],
[7, 8, 9]] [7, 8, 9]]
提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 100
-100 <= matrix[i] [j] <= 100

（1）动态规划

这题其实是第三十四题的一道变形题。

三十四题是从三角形的顶点出发，然后不断转移，直到最后一行，最后在最后一行找出最小的值。本题则是能够从首行的任意位置开始转移。所以解法是和三十四题一模一样的。

完整代码如下：第 14 ~ 19 行：和三十四题思路一致，可以兼顾到三种情况——第 1 列、中间列、最后 1 列。

class Solution {
  int MAX = Integer.MAX_VALUE;
  public int minFallingPathSum(int[][] mat) {
    int n = mat.length;
    int[][] f = new int[n][n];
    // 初始化：对于首行而言，每个位置的「最小成本」就是其「矩阵值」
    for (int i = 0; i < n; i++) f[0][i] = mat[0][i];
    
    // 从第二行开始，根据题目给定的条件进行转移
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < n; j++) {
        // 取出当前格的值
        int val = mat[i][j];
        // 将当前格加上 上面一格的值
        f[i][j] = f[i - 1][j] + val;
        // 不在第1列时执行的代码
        if (j - 1 >= 0) f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val);
        // 不在最后1列执行的代码
        if (j + 1 <  n) f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val);
      }
    }
    
    int ans = MAX;
    for (int i = 0; i < n; i++) ans = Math.min(ans, f[n-1][i]);
    return ans;
  }
}

时间复杂度： $O ( n^{2} )$
空间复杂度： $O ( n^{2} )$

【碎碎念：在做华为机试时，就遇到这类问题，可惜当前没有系统地学习过动态规划的算法，不然应该可以满分。。。

题目是这样的：有三个机器 A、B、C，每次只能运行一个机器来执行任务，每个机器不能相邻运行，不同机器执行相同任务消耗时间不一样，然后求出最少的运行时间。

标准的动态规划，和上面的思路一致，当时用了贪心，只过了 30%。如果之后再有机会做华为机试，不知道会不会抽到图论和树之类的题😵】

三十六、下降路径最小和

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485187&idx=1&sn=a07f67501aa696a79b1e85bb2860c0b2&chksm=fd9cac1ccaeb250a777f9334c0cd3bb0135dafa0007d6d0bbb5cf38e484773d3539fd776b2ea&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「1289. 下降路径最小和 II」**，难度为 Hard。
给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
请你返回非零偏移下降路径数字和的最小值。
这是 LeetCode 上的**「1289. 下降路径最小和 II」**，难度为 Hard。
给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
请你返回非零偏移下降路径数字和的最小值。
示例 1：
输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],[2,4,8], [2,4,9], [2,6,7], [2,6,8],[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
提示：
1 <= arr.length == arr[i].length <= 200
-99 <= arr[i] [j] <= 99

（1）动态规划

最直接的解法依旧是枚举每一个，而每一格的状态转移条件是，上一行除了本列的所有列，这时就需要遍历上一行找出其中最小值。这种解法时间复杂度 O ( n³ )，而数组长度是 10² ，总的时间复杂度为 10⁶ ，可以通过。

class Solution {
  public int minFallingPathSum(int[][] arr) {
    int n = arr.length;
    int[][] f = new int[n][n];
    // 初始化首行的路径和
    for (int i = 0; i < n; i++) f[0][i] = arr[0][i];
    
    // 从第二行进行转移
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < n; j++) {
        f[i][j] = Integer.MAX_VALUE;
        int val = arr[i][j];
        
        // 枚举上一行的每个列下标
        for (int p = 0; p < n; p++) {
          // 只有列下标不同时，才能更新状态
          if (j != p) {
            f[i][j] = Math.min(f[i][j], f[i-1][p] + val);
          }
        }
      }
    }
    
    // 在所有的 f[n - 1][i] 中取最小值
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
      ans = Math.min(ans, f[n-1][i]);
    }
    return ans;
  }
}

时间复杂度： $O ( n^{3} )$
空间复杂度： $O ( n^{2} )$

（2）优化

在运行到某一行时，会发现每次都要重复地遍历上一行，来找出最小值。
初步想一想：如果第 1 列遍历出了最小值，后面的列就不需要再遍历了。
获取次小值：如果某一列与最小值相同列，则需要找出上一行的次小值。

下面代码为在数组中寻找最小值和次小值，以及他们的下标：

有两种情况需要更新数据：

当前数 < 最小值：该数变为最小值，之前的最小值变为次小值
最小值 < 当前数 < 次小值：该数变为次小值

public void findMin(int[] array, int[] tool) {
  int minNum = Integer.MAX_VALUE;
  int minIndex = -1;
  int minSecondNum = Integer.MAX_VALUE;
  int minSecondIndex = -1;
  
  for (int i = 0; i < array.length; i++) {
    int num = array[i];
    // 当前数 < 最小值
    if (num < minNum) {
      minSecondNum = minNum;
      minSecondIndex = minIndex;
      minNum = num;
      minIndex = i;
    }else if (num < minSecondNum) {
      // 如果运行到这一行，必然是当前数 > 最小值，
      // 所以只用判断是否当前数 < 次小值
      minSecondNum = num;
      minSecondIndex = i;
    }
  }
  
  // 更新工具数组
  // 第1格为最小值
  tool[0] = minNum;
  // 第2格为最小值下标
  tool[1] = minIndex;
  // 第3格为次小值
  tool[2] = minSecondNum;
  // 第4格为次小值下标
  tool[3] = minSecondIndex;
}

在主要代码中，先找出第一行的数据，再在每行循环的结束前更新数据。

class Solution {
  public int minFallingPathSum(int[][] grid) {

    int ans = Integer.MAX_VALUE;
    int m = grid.length;
    int n = grid[0].length;
    int[] tool = new int[4];

    // 初始化数据
    findMin(grid[0], tool);

    for (int i = 1; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (j == tool[1]) {
          grid[i][j] += tool[2];
        } else {
          grid[i][j] += tool[0];
        }
      }
      // 在每行循环的结束前更新数据
      findMin(grid[i], tool);
    }

    for (int i = 0; i < n; i++) {
      ans = Math.min(ans, grid[m - 1][i]);
    }
    return ans;
  }
}

（3）进一步优化

由第（2）点可知，我们需要每次遍历上一行。我们发现，在动态规划的过程中，有遍历上一行的动作，毕竟只有遍历完上一行，才会到达当前行。我们可以在动态规划的过程中，同时记录最小值和次小值。

class Solution {
  int MAX = Integer.MAX_VALUE;
  public int minFallingPathSum(int[][] arr) {
    int n = arr.length;
    int[][] f = new int[n][n];

    // i1 代表最小值列下标，i2 代表次小值列下标
    int i1 = -1, i2 = -1;

    // 先遍历第一行，初始化最小值和次小值
    for (int i = 0; i < n; i++) {

      // 更新动规值
      int val = arr[0][i];
      f[0][i] = val;

      // 更新最小值和次小值
      if (val < (i1 == -1 ? MAX : f[0][i1])) {
        i2 = i1;
        i1 = i;
      } else if (val < (i2 == -1 ? MAX : f[0][i2])) {
        i2 = i;
      }
    }

    // 再遍历剩余行
    for (int i = 1; i < n; i++) {

      // 使用临时变量保存当前行的「最小值列下标」&「次小值列下标」
      int ti1 = -1, ti2 = -1;

      // 遍历当前行的所有列
      for (int j = 0; j < n; j++) {
        f[i][j] = MAX;
        int val = arr[i][j];

        // 更新动规值
        // 如果当前列不等于最小值的列，选择最小值
        if (j != i1) {
          f[i][j] = f[i - 1][i1] + val;
        } else {
          // 否则选择次小值
          f[i][j] = f[i - 1][i2] + val;
        }

        // 更新 ti1 和 ti2
        if (f[i][j] < (ti1 == -1 ? MAX : f[i][ti1])) {
          ti2 = ti1;
          ti1 = j;
        } else if (f[i][j] < (ti2 == -1 ? MAX : f[i][ti2])) {
          ti2 = j;
        }
      }

      // 将当前行的最小值和次小值更新变量
      i1 = ti1; i2 = ti2;
    }
    
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
      ans = Math.min(ans, f[n-1][i]);
    }
    return ans;
  }
}

最后将时间复杂度优化到 n² ：

时间复杂度： $O ( n^{2} )$
空间复杂度： $O ( n^{2} )$