动态规划
给定一个三角形, 找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如,给定三角形:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
使用 DFS:
// 会超时
public int minimumTotal(List<List<Integer>> triangle) {
return dfs(0, 0, triangle);
}
// 返回值表示从x, y处到底部的最小路径和
private int dfs(int x, int y, List<List<Integer>> triangle, int[][] saves) {
if (x == triangle.size() - 1) {
return triangle.get(x).get(y);
}
int minLeft = dfs(x + 1, y, triangle, saves);
int minRight = dfs(x + 1, y + 1, triangle, saves);
return Math.min(minLeft, minRight) + triangle.get(x).get(y);
}
优化 DFS,缓存已经被计算的值(称为:记忆化搜索 本质上:动态规划)
public int minimumTotal(List<List<Integer>> triangle) {
int[][] saves = new int[triangle.size()][triangle.size()];
return dfs(0, 0, triangle, saves);
}
// 使用saves数组记录已经被计算过的值
// 返回值表示从x, y处到底部的最小路径和
private int dfs(int x, int y, List<List<Integer>> triangle, int[][] saves) {
if (x == triangle.size() - 1) {
return triangle.get(x).get(y);
}
// 如果已经被计算过则直接返回
if (saves[x][y] != 0) {
return saves[x][y];
}
int minLeft = dfs(x + 1, y, triangle, saves);
int minRight = dfs(x + 1, y + 1, triangle, saves);
// 缓存已经被计算的值
saves[x][y] = Math.min(minLeft, minRight) + triangle.get(x).get(y);
return saves[x][y];
}
动态规划就是把大问题变成小问题,并解决了小问题重复计算的方法称为动态规划
动态规划和 DFS 区别
- 二叉树 子问题是没有交集,所以大部分二叉树都用递归或者分治法,即 DFS,就可以解决
- 像 triangle 这种是有重复走的情况,子问题是有交集,所以可以用动态规划来解决
public int minimumTotal(List<List<Integer>> triangle) {
// 1、状态定义:f[i][j] 表示从i,j出发,到达最后一层的最短路径
int[][] dp = new int[triangle.size()][triangle.size()];
// 2、初始化
for (int i = 0; i < triangle.size(); i++) {
dp[triangle.size() - 1][i] = triangle.get(triangle.size() - 1).get(i);
}
// 3、递推求解
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
}
}
// 4、结果
return dp[0][0];
}
public int minimumTotal(List<List<Integer>> triangle) {
// 1、状态定义:dp[i][j] 表示从0,0出发,到达i,j的最短路径
int[][] dp = new int[triangle.size()][triangle.size()];
// 2、初始化
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
for (int j = 0; j < triangle.get(i).size(); j++) {
// 这里分为三种情况:
// 1、上一层没有左边值
// 2、上一层没有右边值
// 3、其他
if (j == 0) {
dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
} else if (j == triangle.get(i).size() - 1) {
dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
} else {
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
}
}
}
// 从最后一层中查找最小值
int minValue = dp[triangle.size() - 1][0];
for (int i = 0; i < triangle.size(); i++) {
minValue = Math.min(minValue, dp[triangle.size() - 1][i]);
}
return minValue;
}
经过观察发现当前状态只与上一批状态有关,所以二维数组可以优化为一位数组,减少空间占用。
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.size()];
for (int i = 0; i < triangle.size(); i++) {
dp[i] = triangle.get(triangle.size() - 1).get(i);
}
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
除此之外,也可以覆盖原有数据以实现空间复用。
满足两个条件
- 满足以下条件之一
- 求最大/最小值(Maximum/Minimum )
- 求是否可行(Yes/No )
- 求可行个数(Count(*) )
- 满足不能排序或者交换(Can not sort / swap )
- 1.状态 State
- 灵感,创造力,存储小规模问题的结果
- 2.方程 Function
- 状态之间的联系,怎么通过小的状态,来算大的状态
- 3.初始化 Intialization
- 最极限的小状态是什么, 起点
- 4.答案 Answer
- 最大的那个状态是什么,终点
- 1.Matrix DP (10%)
- 2.Sequence (40%)
- 3.Two Sequences DP (40%)
- 4.Backpack (10%)
注意点
贪心算法大多题目靠背答案,所以如果能用动态规划就尽量用动规,不用贪心算法
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
public int minPathSum(int[][] grid) {
// dp[i][j] 表示0,0到i,j的最小和
int[] dp = new int[grid[0].length];
// 初始化:用第一行初始化
dp[0] = grid[0][0];
for (int i = 1; i < grid[0].length; i++) {
dp[i] = dp[i-1] + grid[0][i];
}
// 状态转移方程
// 每行第一个元素:
// dp[j] = dp[j](到上一行这个位置的最小和) + grid[i][j];
// 后续元素:
// dp[j] = Math.min(dp[j-1](到左边位置的最小和), dp[j](到上一行这个位置的最小和)) + grid[i][j];
for (int i = 1; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (j == 0) {
dp[j] = dp[j] + grid[i][j];
} else {
dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
}
}
}
// 答案
return dp[grid[0].length - 1];
}
一个机器人位于一个 m x n 网格的左上角 (起始点在下图 中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?
public int uniquePaths(int m, int n) {
// dp[i][j] 表示0,0到i,j的路径数
int[] dp = new int[n];
// 初始化:到达第一行的路径数均为1
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
// 每行第一个格子只有一条路到达
if (j == 0) {
dp[j] = 1;
}
// 其他格子可以由左侧或上方的格子到达
else {
dp[j] = dp[j-1] + dp[j];
}
}
}
return dp[n-1];
}
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];
// 初始化:遇到障碍前仅有一条路,之后全为0
dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
for (int i = 1; i < n; i++) {
if (obstacleGrid[0][i] == 1) {
dp[i] = 0;
} else {
dp[i] = dp[i-1];
}
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
// 当前格是障碍,不可达,置为0
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (j > 0) {
dp[j] = dp[j-1] + dp[j];
}
}
}
return dp[n-1];
}
public int climbStairs(int n) {
int[] dp = new int[]{0, 1};
while (n > 0) {
int temp = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = temp;
n--;
}
return dp[1];
}
给定一个无序的整数数组,找到其中最长上升子序列的长度。
public int lengthOfLIS(int[] nums) {
// dp[i]表示从0到i的最长上升子序列长度
int[] dp = new int[nums.length];
// 初始化:到第一个元素序列长度为1
dp[0] = 1;
for (int i = 1; i < nums.length; i++) {
// 注意默认为1,即此处最长子序列为自身
int maxLen = 1;
// dp[i] = max(dp[j]) + 1 , nums[j] < nums[i]
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
maxLen = Math.max(maxLen, dp[j] + 1);
}
}
dp[i] = maxLen;
}
int maxNum = 0;
for (int n : dp) {
maxNum = Math.max(maxNum, n);
}
// 答案:dp中的最大值
return maxNum;
}
给定一个