目录
0.动态规划问题
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题,进行解决，从而一步步获取最优解的处理算法
动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用
对于动态规划问题,大致可以分为以下几步:
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
一.爬楼梯
1.题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
力扣:力扣
2.问题分析
对于解决这样的动态规划的背包问题,还是采用通用的五个步骤
1.确定dp数组（dp table）以及下标的含义
dp[i]的含义为爬到i层台阶一共有dp[i]种方法
2.确定递推公式
因为每一次可以选择爬1或2个台阶,所以爬到第i层台阶,可以选择从i-2层(爬2层台阶)到达,也可以选择从i-1层(爬一层台阶)台阶到达,所以爬到第i层的方法数(dp[i])等于爬到第i-2层的方法数(dp[i-2])加上爬到第i-1层的方法数(dp[i-1])
所以递推公式为:dp[i]=dp[i-1]+dp[i-2]
dp[i] = dp[i - 1] + dp[i - 2];3.dp数组如何初始化
由递推公式可知,推出dp[i]需要前两项的值,因此进行初始化的时候,至少对dp[0]和dp[1]进行初始化赋值,但这个时候dp[0]应该是爬到第0层的方法数,这个时候生活常识,不可能有第0层,这个时候我们应该选择dp[1]和dp[2]进行初始化,爬到第一层就一种,爬一层台阶,爬到第二层可以有两种,第一种直接爬到第二层,也可以借助第一层爬到第二层
dp[1] = 1;
dp[2] = 2;4.确定遍历顺序
由递推公式可知,推出dp[i]需要前两项的递推出来,所以应该按照从从下到上(从低台阶到高台阶)的遍历顺序
5.举例推导dp数组
当n=5时候进行填表
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| dp[i] | 0 | 1 | 2 | 3 | 5 | 8 |
3.代码实现
public int climbStairs(int n) {
if (n == 1)
return 1;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}二.使用最小花费爬楼梯
1.题目描述
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
力扣:力扣
2.问题分析
对于解决这样的动态规划的背包问题,还是采用通用的五个步骤
1.确定dp数组（dp table）以及下标的含义
dp[i]的含义:爬到第i个台阶的最低花费
2.确定递推公式
由题意可知,每一次可以爬一个或者两个台阶,所以可以选择从i-2层,支付第i-2层的花费直接爬到第i层,也可以选择从i-1层,支付第i-1层的花费直接爬到第i层,只需要从中选择最低的那一个就可以了,所以递推公式为:dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
3.dp数组如何初始化
从递推公式可以看出,需要前两项的支撑才可以推出后面一项,所以至少需要对dp[0]和dp[1],这里可以很清楚的直到爬到第0层就不需要花费,直接跳到第0层台阶,因此dp[0]=0,同样的爬到第1层也不需要花费,因为此时可以直接跳两步到达第二层dp[1]=0
dp[0] = 0;
dp[1] = 0;4.确定遍历顺序
由递推公式可知,推出dp[i]需要前两项的递推出来,所以应该按照从从下到上(从低台阶到高台阶)的遍历顺序
5.举例推导dp数组
对于cost={1,100,1,1,1,100,1,1,100,1}进行填表
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| dp[i] | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 6 |
3.代码实现
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i < cost.length + 1; ++i) {
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[cost.length];
}三. 爬楼梯(进阶版)
1.题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以weight数组中的步数(如:weight={1,2,3},意思为每次可以爬1个或者2个,或者3个台阶)。你有多少种不同的方法可以爬到楼顶呢？
力扣:力扣
2.问题分析
对于这个问题,前面我们用了最直接的动态规划问题来解决,当我们学习了背包问题之后,我们可以用这个思想来解决这个问题,因为我们每次可以爬1个或者2个,每一次都可以在1个和2个来进行选择,爬几层的这个问题就相当于背包中的物品,n级台阶相当于背包的重量,这样就转换为了多重背包的问题,同时,当可以爬更多次(如:一次可以爬1层或2层或3层……..)台阶的时候,多重背包来解决这个问题是更好的.(背包问题指路:Java之动态规划的背包问题_允歆辰丶的博客-CSDN博客)
1.确定dp数组（dp table）以及下标的含义
dp[i]的含义是:爬到第i层台阶,有dp[i]中方法
2.确定递推公式
当我们需要到达第i层台阶的时候,此时我们可以选择的是爬1个还是2个(或更多)台阶到达第i层台阶,当我们一步到达的时候dp[i]+=dp[i-1],当我们两步到达的时候dp[i]+=dp[i-2]…….
因此当步数的数组为weight的时候,递推公式
dp[i]+=dp[i-weight[j]]
dp[j] += dp[j - weight[i]];3.dp数组如何初始化
我们需要初始化的就是爬到第0层台阶的方法,此时需要一种方法,将dp[0]初始化为1
dp[0] = 1;4.确定遍历顺序
多重背包问题,遍历方式从左到右
5.举例推导dp数组
| 第一次 | |||||
| 1 | 0 | 0 | 0 | 0 | 0 |
| 第二次 | |||||
| 1 | 1 | 0 | 0 | 0 | 0 |
| 第三次 | |||||
| 1 | 1 | 2 | 0 | 0 | 0 |
| 第四次 | |||||
| 1 | 1 | 2 | 3 | 0 | 0 |
| 第五次 | |||||
| 1 | 1 | 2 | 3 | 5 | 0 |
| 第六次 | |||||
| 1 | 1 | 2 | 3 | 5 | 8 |
3.代码实现
int[] weight = {1, 2};
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 0; j <= n; ++j) {//遍历楼梯
for (int i = 0; i < weight.length; ++i) {//遍历上台阶的步数
if (j >= weight[i])//当楼梯的数量大于等于上台阶的步数
dp[j] += dp[j - weight[i]];
}
}
return dp[n];四.坏掉楼梯的爬楼梯问题
1.题目描述
假设你要爬楼梯。楼梯一共有 n 层台阶。因为腿长的限制，每次最多能上 4 层台阶。但是第 5,7 层楼梯坏掉了不能踩。求上楼梯的方案数。
2.问题分析
这一题与上一题唯一不同的点就是出现了有些楼梯不能踩的限制,其实这里可以直接使dp[5]和dp[7]的方法数为0,这样相当于每次都不经过第5和第7层而到达别的楼层
举例推导dp数组
j=0
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j=1
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]j=2
[1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0]j=3
[1, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0]j=4
[1, 1, 2, 4, 8, 0, 0, 0, 0, 0, 0]j=6
[1, 1, 2, 4, 8, 0, 14, 0, 0, 0, 0]j=8
[1, 1, 2, 4, 8, 0, 14, 0, 22, 0, 0]j=9
[1, 1, 2, 4, 8, 0, 14, 0, 22, 36, 0]j=10
[1, 1, 2, 4, 8, 0, 14, 0, 22, 36, 72]
3.代码实现
public static int climbStairs(int n) {
int[] weight = {1, 2, 3, 4};
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 0; j <= n; ++j) {//遍历楼梯
if (j == 5 || j == 7)
continue;
for (int i = 0; i < weight.length; ++i) {//遍历上台阶的步数
if (j >= weight[i])//当楼梯的数量大于等于上台阶的步数
dp[j] += dp[j - weight[i]];
}
}
return dp[n];
}五.第39级台阶
1.题目描述
假设你要爬楼梯。楼梯一共有 n 层台阶。如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的方法呢？
2.问题分析
这题与之前题目不同的就是偶数步和奇数步的判断,之前的dp数组是无法判定奇数步还是偶数步的,因此这里需要对dp数组进行一定的改变
1.确定dp数组（dp table）以及下标的含义
我们可以增加一个维度,用来存储偶数步和奇数步的方法数,选择二维dp数组dp[][]的含义是:爬到第i层台阶,走偶数步的有dp[i][0]中方法,走奇数步有dp[i][1]种方法
2.确定递推公式
先来分析偶数步到达第i层的递推公式,此时一样可以由奇数步的走一个和两个台阶到达第i层,
此时dp[i][0]=dp[i-1][1]+dp[i-2][1]
再来来分析奇数步到达第i层的递推公式,此时一样可以由偶数步的走一个和两个台阶到达第i层,
此时dp[i][1]=dp[i-1][0]+dp[i-2][0]
3.dp数组如何初始化
由递推公式可知,至少初始化dp[1][0],dp[1][1],dp[2][0],dp[2][1]
dp[1][0]:偶数步不可能到达第一层dp[1][0]=0,爬一级台阶到达第一层,奇数步dp[1][1]=1
dp[2][0]:先爬一层到达第一层,在爬一层到达第二层,一种方法,dp[2][0]=1
dp[2][1]:直接爬两个台阶到达第二层,dp[2][1]=1;
dp[1][0]=0;
dp[1][1]=1;
dp[2][0]=1;
dp[2][1]=1;4.确定遍历顺序
由递推公式可知,推出dp[i]需要前两项的递推出来,所以应该按照从从下到上(从低台阶到高台阶)的遍历顺序
5.举例推导dp数组
过多,不进行推导了
3.代码实现
public static int climbStairsEven(int n) {
int[][] dp = new int[n + 1][2];
dp[1][0] = 0;
dp[1][1] = 1;
dp[2][0] = 1;
dp[2][1] = 1;
for (int i = 3; i <= 39; ++i) {
dp[i][0] = dp[i - 1][1] + dp[i - 2][1];
dp[i][1] = dp[i - 1][0] + dp[i - 2][0];
}
return dp[n][0];
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101052.html
