学习资料
代码随想录
动态规划五部曲
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
简单题
509. 斐波那契数 - 力扣(LeetCode)
70. 爬楼梯 - 力扣(LeetCode)
可以先尝试自己用dp五部曲,把原来的递归方法转为动态规划
动态规划通过把结果保存在dp数组中,避免了递归中的重复工作
从而降低了代码的时间复杂度
难度升级!!!
题目一:使用最小花费爬楼梯
问题描述
746. 使用最小花费爬楼梯 - 力扣(LeetCode)
给你一个整数数组 cost
,其中 cost[i]
是从楼梯第 i
个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
解题步骤
首先需要明确一下题意,题目要求可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯
那么就是说我们一开始站在0/1这节台阶上是0花费的
最终我们的目标有两个
一是跳到楼梯顶部(第i+1个台阶,不是第i个台阶!不然为什么要有cost[i]呢你说?)
二是实现最低花费
接着开始使用动态规划五部曲,格式化做题有助于前期的理解与掌握
1.确定dp数组(dp table)以及下标的含义
这里肯定选用一维数组dp[i]
i代表第i节台阶,dp[i]存放的是到达第i节台阶所需的最小花费
dp[i]//到达第i节台阶的最小花费
2.确定递推公式
根据跳台阶的简单题,我们可以知道dp[i]的值与dp[i-1],dp[i-2],cost[i-1],cost[i-2]有关,
因为第 i 节台阶可以从第 i - 1 节台阶跳一步到达,也可以从第 i - 2 节台阶直接跳两级到达
dp[i-1]+cost[i-1]代表在到达第i-1节台阶需要的最小花费为dp[i-1],继续到达第i节还需要花费cost[i-1]
但由于最后我们需要的是最小花费,所以dp[ i ] 的值应该取这两者的最小值
即 dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3.dp数组如何初始化
初始化就是要找到最初状态进行赋值
很显然最初状态就是起跑线嘛
dp[0]=0,dp[1]=1
4.确定遍历顺序
这一题没什么弯弯绕绕的,从头开始跳就完了
for(int i=2;i<=cost.size()+1;i++)
5.举例推导dp数组
这一步可以用在检查代码问题,这里不多赘述
组合这5步,得到
vector<int> dp(cost.size()+1);
dp[0]=0;
dp[1]=0;
for(int i=2;i<=cost.size();i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.size()];
就这么简单!恭喜获得dp小试牛刀称号一枚!
题目二:不同路径
问题描述
62. 不同路径 - 力扣(LeetCode)
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
解题步骤
动态规划五部曲
1.确定dp数组(dp table)以及下标的含义
由于是m x n的网格,我们应该也用二维数组作为dp的数据结构
那么dp[i][j]就是走到当前格(第i行第j列)的路径数
最后需要返回的是dp[m-1][n-1]
vector<vector<int>> dp(m,vector<int> n);//注意二维数组的定义!
2.确定递推公式
按照移动规律,每次只能向下或者向右移动一步
那么[ i ][ j ]这一格可以从[ i-1 ][ j ]走过来,也可以从[ i ][ j-1 ]走过来
所以
dp[i][j]=dp[i-1][j]+dp[i][j-1]
容易出现的误区:认为dp[i][j]=(dp[i-1][j]+1)+(dp[i][j-1]+1)
这样做就是没想明白dp数组的真实含义,我们不是在统计走了几格
而是在统计路径数,从[ i-1 ][ j ]到[ i ][ j ]这一步并不是多了一个新路径,而是原路径的延续而已
路径的增多就只体现在这两种方案选择加起来
3.dp数组如何初始化
从[0][0]开始行动!
那么我们首先想到的肯定是 dp[0][1]=1;dp[1][0]=1
但仔细思考一下,只能向下或者向右走
那我们需要初始化的其实是第一行和第一列的所有元素
他们的值都应该为1,只能一条道走到黑!
for(int i=0;i<m;i++){
dp[i][0]=1;
}
for(int j=0;j<n;j++){
dp[0][j]=1;
}
4.确定遍历顺序
遍历顺序应该接着初始化内容继续往下生成,又要保证每一格格子都填上
所以应该从1开始
for(int i=1;i<m;i++){
for(int j=1;j<n;j++{
5.举例推导dp数组
这一步还是看情况使用啦
那么整体代码如下:
class Solution {
public:int uniquePaths(int m, int n) {//定义 dp[i][j]指走到这个格有几种路径vector<vector<int>> dp(m, vector<int>(n));//初始化//需要给第一行第一列都得初始化为1,才能确保它按照规则走!//dp[0][0]=0;for(int i=0;i<m;i++){dp[i][0]=1;}for(int j=0;j<n;j++){dp[0][j]=1;}//遍历for(int i=1;i<m;i++){for(int j=1;j<n;j++){//递推公式 每一个位置可以由上面或者左边走过来dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
};
做完这一题可以尝试一下进阶版:
63. 不同路径 II - 力扣(LeetCode)
加了一点障碍,整体思路是大差不差的!
只是要在关键处加入对障碍的判断即可
题目三:整数拆分
问题描述
343. 整数拆分 - 力扣(LeetCode)
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
解题步骤
初看这一题,我认为就是往拆成尽可能大的两个数(最好是一人一半)进行相乘
这样后面的数字可以利用前面的数字继续两两相乘即可
但仔细一看,将其拆成k个正整数和,那么就不止掰两半,并且掰三份还真的有可能更大
比如示例2:输入10,如果拆成两个5,两数之积才25,拆成3 3 4,乘积就是36
虽然拆分思路不对,但是这些数字取最大乘积肯定还是存在递推关系的
那么我们就还是用动态规划五部曲一步一步来!
但是此处我认为可以调换一下五部曲顺序,先把我们能做的做好!
1.确定dp数组(dp table)以及下标的含义
没有任何二维的特征,肯定用一维数组dp[ i ]
i 表示当前值,dp[ i ]表示这个数拆分后的最大乘积
我们需要不断拆分i,去取得最大乘积
vector<int> dp(n+1);
2.dp数组如何初始化
初始化这一步既简单又关键
我们只需要想想最开始的几个有无特殊,做一个设置即可
对于0,1不能拆分为正整数,我们不做初始化
所以只有2需要提前设定一下!
dp[2]=1
3.确定遍历顺序
因为拆分有多种情况,所以我们需要在范围内遍历所有情况
那么设置内外两层循环
外循环用于遍历i
内循环用于拆分,用 j 遍历所有结果
for(int i=3;i<=n;i++){
for(int j=1;j<i;j++){
4.确定递推公式
这一块是本题的重点!
按照前面的逻辑dp[ i ] = dp[ j ] * dp[ i -j ]
就是把i拆成了 j,i-j两个数,然后当前值拆分后的乘积 应该是这两者最大乘积的 乘积
但这样有点思维定势了,我们得到乘积的方法不止这一个
直接相乘也是它的乘积 dp[i] = j *(i-j) ,我们并不能确定哪个更大
可能直接想有点抽象,我们举例来说
i=4,j=2 //4被拆成2*2的情况
dp[4] = dp[2] * dp[2] = 1*1=1
dp[4] = 2 * 2 =4
所以我们需要在这两种方案中取最大值
dp[i] = max(dp[ j ] * dp[ i-j ]), j * ( i - j ))
ok,想到这是不是就觉得结束了呢?run一下就发现完全对不上!
因为我们还忽略了两件事情,
第一件:对于一个i 我们需要决出唯一的最大值,
但我们并没有在所有方案中找最大值啊
所以递推公式应该改为
dp[i] = max ( max(dp[ j ] * dp[ i-j ]), j * ( i - j )) , dp[i])//括号里的dp[i]指的是上一个方案的最大值!
第二件:使用dp就代表我们对该数字进行了拆分
但一个数字不需要两遍同时拆分,这里会有重复
例如:5可以分为 1和4,2和3,3和2,4和1
j 值不断改变是可以得到所有情况的(实际上前两种和后两种一样嘛)
那么也就是说dp[ i -j ]会对1,2,3,4都进行dp操作(执行dp就是开始拆分,经过递推就会有多种拆分方法生成)
那么重复的dp[j]就没有必要
所以最后应该改为
dp[i]=max(max(j*(i-j),j*dp[i-j]),dp[i]);
ok到这一步我们的程序就没有问题啦
完整代码如下:
class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);//第i个数字拆分后的最大乘积为dp[i]//初始化//0,1,不可拆分为正整数,没有初始化意义!dp[2]=1;//遍历for(int i=3;i<=n;i++){//拆分for(int j=1;j<i;j++){//递推公式dp[i]=max(max(j*(i-j),j*dp[i-j]),dp[i]);//dp[i]=max(j*(i-j),j*dp[i-j]);}}return dp[n];}
};