动态规划day2345【代码随想录学习】
动态规划五部曲
- 1、确定dp数组以及下标含义
- 2、确定递推公式---->状态转移方程
- 3、dp数组如何初始化
- 4、确定遍历顺序
- 5、举例推导dp数组（如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。）
int fib(int n){ if (n <= 1){ return n; } vector dp(n+1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];
}
使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
1、确定dp数组以及下标含义：
dp[i]:到达第i台阶所花费的最少力气为dp[i]
2、确定递推公式
dp[i] = min(dp[i-1] +cost[i-1],dp[i-2]+cost[i-2]);
3、dp数组初始化
dp[0]=0;
dp[1]=0;
4、确定遍历顺序
顺序遍历
5、举例推导dp数组
int minCostClimbingStairs(vector& cost){ vector 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()];}
int main(){ vector cost = {1,100,1,1,1,100,1,1,100,1}; cout< 如果代码写出来了，一直AC不了，灵魂三问：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
不同路径 力扣题目链接
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
- 输入：m = 3, n = 7
- 输出：28
示例 2：
- 输入：m = 2, n = 3
- 输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
int uniquePaths(int m,int n){vector> dp(m,vector(n,0));//定义一个m*n二维数组，所有元素置为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];
}
不同路径Ⅱ 力扣题目链接
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
- 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
- 输出：2 解释：
- 3x3 网格的正中间有一个障碍物。
- 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2： 
- 输入：obstacleGrid = [[0,1],[0,0]]
- 输出：1
提示：
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
int uniquePathsWithObstacles(vector>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); if (obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1){ return 0;
// cout<<"no";
} vector> dp(m,vector(n,0)); for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) dp[i][0] = 1; for (int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) dp[0][j] = 1; for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (obstacleGrid[i][j] == 1) continue; dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } /* for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { cout< 整数拆分 力扣题目链接
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
- 输入: 2
- 输出: 1
- 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
- 输入: 10
- 输出: 36
- 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
- 说明: 你可以假设 n 不小于 2 且不大于 58。
动规五部曲，分析如下：
-
1、确定dp数组（dp table）以及下标的含义
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
-
2、确定递推公式
可以想 dp[i]最大乘积是怎么得到的呢？其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。
一个是j * dp[i - j]，相当于是拆分(i - j)。
j怎么就不拆分呢？
j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。那么从1遍历j，比较(i - j) * j和dp[i - j] * j 取最大的。
递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
也可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。
所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
那么在取最大值的时候，为什么还要比较dp[i]呢？
因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。
-
3、dp的初始化
严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。
拆分0和拆分1的最大乘积是多少？这是无解的。
这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！
-
4、确定遍历顺序
确定遍历顺序，先来看看递归公式：
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。
-
5、举例推导dp数组
举例当n为10 的时候，dp数组里的数值，如下：
class Solution {
public:int integerBreak(int n) {vector dp(n + 1);dp[2] = 1;for (int i = 3; i <= n ; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};