算法通关村第十九关 | 青铜 | 动态规划

1.统计路径总数（递归）

原题：力扣62.

每次移动都是将问题规模缩小。

要理解：return search(m - 1, n) + search(m, n - 1);

public class Solution {
    public int uniquePaths (int m, int n) {
        return search(m, n);
    }
    public int search(int m, int n) {
        // 就剩一行或一列，只有一条路径，递归结束
        if (m == 1 || n == 1) {
            return 1;
        }
        // 分解为两个更小的矩阵之和
        return search(m - 1, n) + search(m, n - 1);
    }
}

2.使用二维数组优化递归（记忆化搜索）

原题：力扣62.

相同大小的矩阵已经计算过了，就不需要再计算了，这个是记忆化搜索。

public int uniquePaths(int m, int n) {
	int[][] f = new int[m][n];
    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) {
            	f[i][j] = f[i - 1][j];
        	} else if (j > 0) {
            	f[i][j] = f[i][j - 1];
        	}
        } 
    }
    return f[m - 1][n - 1];
}

3.滚动数组（一维数组代替二维数组）

原题：力扣62.

滚动数组：反复更新数组。

这样的写法包括了重复子问题，记忆化搜索，滚动数组，是一个简单的动态规划。

公式：dp[j] = dp[j] + dp[j - 1]

public int uniquePaths(int m, int n) {
	int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // dp[j] 用的是上一行的， dp[j - 1] 用的是已经更新的同行的前一位
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
}

4.最小路径和（拓展）

原题：力扣64.

状态转移方程：f[i][j] = min{f[i-1][j],f[i][j-1]} + A[i][j]

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++) {
            if (i == 0 && j == 0) {
                f[i][j] = grid[i][j];
            } else {
                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];
}

5.三角形最小路径和（拓展）

原题：力扣120.

可以用无后效性来分析是否可以使用动态规划，如果当前状态确定后，之后的状态转移与之前的决策无关，那么就可以使用动态规划。

public int minimumTotal(List<List<Integer>> tri) {
	int n = tri.size();
    int ans = Integer.MAX_VALUE;
    int[][] f = new int[n][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][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);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, f[n - 1][i];
    }
    return ans;
}

如果对您有帮助，请点赞关注支持我，谢谢！ ?
如有错误或者不足之处，敬请指正！ ?
个人主页：星不易 ?
算法通关村专栏：不易|算法通关村 ?