学习资料
代码随想录
动态规划五部曲
- 确定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];}
};
