算法训练营Day25动态规划part1
目录
【算法训练营Day25】动态规划part1
本文章已经生成可运行项目，一键运行
理论基础
动态规划，简称DP，使用场景：某一问题有很多重叠子问题
贪心的思想是局部最优推导出全局最优，而dp的重点在于每一个状态一定是由上一个状态推导而来，正因为状态是连续相关的所以我们一般要借助于dp数组以及递推式来解决问题。
DP中比较常见的几类问题：
- 基础题目
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
解题思路：首先想办法把问题化成很多子问题，成功把问题拆分之后，再结合dp数组确定递推公式，根据递推公式确定初始化逻辑以及遍历顺序。
DP问题的解题四部曲：
- 确定dp数组以及下标的含义【重中之重！！！要以结果为导向去分析dp数组的含义】
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
dp问题排查：
把dp数组打印出来，看看究竟是不是按照自己思路推导的！
斐波那契数
题目链接：
用递归做的话，代码如下：
class Solution {
public int fib(int n) {
if(n == 0) return 0;
else if(n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
}如果用动态规划的话，使用dp四部曲：
- 确认数组及下标含义：数组的每个位置对应斐波那契元素的位置
- 确定递推公式：dp[i] = dp[i - 1] + dp[i - 2]
- 确定数组初始化：dp[0] = 0，dp[1] = 1
- 确定数组遍历顺序：从前往后遍历
代码如下：
class Solution {
public int fib(int n) {
if(n == 0) return 0;
else if(n == 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2;i < dp.length;i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}爬楼梯
题目链接：
解题思路：每次只能爬1或2个阶梯，那么
- 爬1阶，有1种办法
- 爬2阶，有2种办法
- 爬3阶，有两种情况在爬2阶的基础上再爬一阶，以及在爬1阶的基础上爬2阶，一共3种
那么本题和上一题基本一样，区别在于数组的含义与初始化方式。
代码如下：
class Solution {
public int climbStairs(int n) {
if(n == 1) return 1;
else if(n == 2) return 2;
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for(int i = 2;i < dp.length;i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1];
}
}使用最小花费爬楼梯
题目链接：
解题思路：
和上一题类似，只不过本题加入了一个消费的逻辑。
dp四部曲：
- 确认数组及下标含义：i表示下标为i的阶梯，dp[i]表示到达下标为i的阶梯要花费的体力
- 确定递推公式：dp[i] = min{dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]}
- 确定数组初始化：dp[0] = 0，dp[1] = 0
- 确定数组遍历顺序：从前往后遍历
代码如下：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length];
dp[0] = 0;
dp[1] = 0;
for(int i = 2;i < dp.length;i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
}
return Math.min(dp[cost.length - 1] + cost[cost.length - 1],dp[cost.length - 2] + cost[cost.length - 2]);
}
}不同路径
题目链接：
解题思路：
本题的关键在于只能向下和向右运动。本题要求起点到终点的路径，我们可以先把问题切小，先找出到到起点右边或者下边有多少条路经，然后一步步递推得到答案。
dp四部曲：
- dp数组以及下标的含义：dp[i][j]表示从起点到（i，j）的路径有多少条
- 递推公式：dp[i][j] = dp[i][j - 1] + dp[i + 1][j]
- 初始化方式：因为dp[i][j]与上面和左边的元素有关，那么初始化的时候先初始化最上面与最左边。又因为只能向下与向右移动，所以第一行与第一列都可以初始化为1
- 遍历顺序：从左向右，从上往下
解题代码：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0;i < m;i++) dp[i][0] = 1;
for(int i = 0;i < n;i++) dp[0][i] = 1;
for(int i = 1;i < m;i++) for(int j = 1;j < n;j++) dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
return dp[m - 1][n - 1];
}
}不同路径 II
题目链接：
解题思路：
和上一题的区别在于有的格子不能走。那么我们在初始化的时候就要注意只要出现了障碍，那么后面都是不可达的！同时在更新dp数组的时候，如果对应的（i，j）处是障碍，那么不可达，路线则是默认的0；
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for(int i = 0;i < m;i++) {
if(obstacleGrid[i][0] == 1) break;
dp[i][0] = 1;
}
for(int i = 0;i < n;i++) {
if(obstacleGrid[0][i] == 1) break;
dp[0][i] = 1;
}
for(int i = 1;i < m;i++) for(int j = 1;j < n;j++) if (obstacleGrid[i][j] == 0) dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
return dp[m - 1][n - 1];
}
}本文已生成可运行项目一键运行
生成项目
