64. 最小路径和
给一个二维数组，然后求最短路径长度问题
不管是动态规划还是递归一上来总是没有思路，真愁人啊，即使看到了递归的思路也不能马上改写成动态规划，我脑袋是木头吧，太笨了
递归解法：
class Solution {
int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 计算从左上角走到右下角的最小路径和
return dp(grid, m - 1, n - 1);
}
int dp(int[][] grid, int i, int j) {
// base case
if (i == 0 && j == 0) {
return grid[0][0];
}
// 如果索引出界，返回一个很大的值，
// 保证在取 min 的时候不会被取到
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
// 左边和上面的最小路径和加上 grid[i][j]
// 就是到达 (i, j) 的最小路径和
return Math.min(
dp(grid, i - 1, j),
dp(grid, i, j - 1)
) + grid[i][j];
}
}
动态规划解法：
class Solution {
// 备忘录
int[][] memo;
int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 构造备忘录，初始值全部设为 -1
memo = new int[m][n];
for (int[] row : memo)
Arrays.fill(row, -1);
return dp(grid, m - 1, n - 1);
}
int dp(int[][] grid, int i, int j) {
// base case
if (i == 0 && j == 0) {
return grid[0][0];
}
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
// 避免重复计算
if (memo[i][j] != -1) {
return memo[i][j];
}
// 将计算结果记入备忘录
memo[i][j] = Math.min(
dp(grid, i - 1, j),
dp(grid, i, j - 1)
) + grid[i][j];
return memo[i][j];
}
}
787. K 站中转内最便宜的航班
这个题目难的不是递归思路，而是将题目表达转成适合递归的数据结构
递归解法：
class Solution {
// 哈希表记录每个点的入度
// to -> [from, price]
HashMap<Integer, List<int[]>> indegree;
int src, dst;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// 将中转站个数转化成边的条数
K++;
this.src = src;
this.dst = dst;
indegree = new HashMap<>();
for (int[] f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
// 记录谁指向该节点，以及之间的权重
indegree.putIfAbsent(to, new LinkedList<>());
indegree.get(to).add(new int[] {from, price});
}
return dp(dst, K);
}
// 定义：从 src 出发，k 步之内到达 s 的最短路径权重
int dp(int s, int k) {
// base case
if (s == src) {
return 0;
}
if (k == 0) {
return -1;
}
// 初始化为最大值，方便等会取最小值
int res = Integer.MAX_VALUE;
if (indegree.containsKey(s)) {
// 当 s 有入度节点时，分解为子问题
for (int[] v : indegree.get(s)) {
int from = v[0];
int price = v[1];
// 从 src 到达相邻的入度节点所需的最短路径权重
int subProblem = dp(from, k - 1);
// 跳过无解的情况
if (subProblem != -1) {
res = Math.min(res, subProblem + price);
}
}
}
// 如果还是初始值，说明此节点不可达
return res == Integer.MAX_VALUE ? -1 : res;
}
}
但是递归超时了，所以需要用动态规划，用空间换时间
class Solution {
// 哈希表记录每个点的入度
// to -> [from, price]
HashMap<Integer, List<int[]>> indegree;
int src, dst;
int[][] memo;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// 将中转站个数转化成边的条数
K++;
this.src = src;
this.dst = dst;
memo = new int[n][K + 1];
for (int[] row : memo) {
Arrays.fill(row, -888);
}
indegree = new HashMap<>();
for (int[] f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
// 记录谁指向该节点，以及之间的权重
indegree.putIfAbsent(to, new LinkedList<>());
indegree.get(to).add(new int[] {from, price});
}
return dp(dst, K);
}
// 定义：从 src 出发，k 步之内到达 s 的最短路径权重
int dp(int s, int k) {
// base case
if (s == src) {
return 0;
}
if (k == 0) {
return -1;
}
// 查备忘录，防止冗余计算
if (memo[s][k] != -888) {
return memo[s][k];
}
// 初始化为最大值，方便等会取最小值
int res = Integer.MAX_VALUE;
if (indegree.containsKey(s)) {
// 当 s 有入度节点时，分解为子问题
for (int[] v : indegree.get(s)) {
int from = v[0];
int price = v[1];
// 从 src 到达相邻的入度节点所需的最短路径权重
int subProblem = dp(from, k - 1);
// 跳过无解的情况
if (subProblem != -1) {
res = Math.min(res, subProblem + price);
}
}
}
// // 如果还是初始值，说明此节点不可达
// return res == Integer.MAX_VALUE ? -1 : res;
// 存入备忘录
memo[s][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[s][k];
}
}
