3.动态规划.基础

基础理论
- 背包基础理论
- - 01背包
  - 完全背包
  - 多重背包
题目
- 1.斐波那契数
- 2.爬楼梯
- 3.使用最小花费爬楼梯
- 4.不同路径
- 5.不同路径2

基础理论

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。（很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题这些）

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。对于动态规划问题，我将拆解为如下五步曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化；因为一些情况是递推公式决定了dp数组要如何初始化
确定遍历顺序；这一点在背包问题中可以体现
举例推导dp数组；找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的

debug时，发出这样的问题之前，其实可以自己先思考这三个问题：（如果这灵魂三问自己都做到了，基本上这道题目也就解决了）
1.这道题目我举例推导状态转移公式了么？
2.我打印dp数组的日志了么？
3.打印出来了dp数组和我想的一样么？

动态规划解决的经典问题：

背包问题
打家劫舍
股票问题
子序列问题
其他（区间DP，概率DP）

背包基础理论

1.01背包（基础-重中之重） 2.完全背包 3.多重背包（知道含义，解法即可）
在这里插入图片描述

01背包

01背包-二维dp数组
有n种物体数量为1个，每个物品有各自的重量，价值，目前有一个载重量为m的背包，尝试尽可能装满的背包并使价值最大。
在这里插入图片描述
暴力解法：每个物品只有取和不取两种状态，所以可以使用回溯算法枚举所有可能，统计出最大的价值。时间复杂度为O(2^n)

动态规划：
1.dp数组的意义：dp[i][j]的定义为：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.递推公式：1.不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)；2.放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值；因此得到 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.初始化：dp[0][slice], dp[slice][0]=0——对于0下标的初始化0；对于非0下标的初始化为任意值都可以。
4.遍历顺序：有两层for循环（一个是物品i，一个背包容量j）；根据dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])需要上方和左上方的数据，因此哪个先遍历都可以。其实都可以！！但是先遍历物品更好理解。
从递归公式dp[i] = dp[i - 1] + dp[i - 2]；中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。

// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}
// 完整代码
void test_2_wei_bag_problem1() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagweight = 4;// 二维数组vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}// weight数组的大小 就是物品个数for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}cout << dp[weight.size() - 1][bagweight] << endl;
}

01背包-滚动数组-一维dp数组
1.dp数组的意义：dp[j]的定义为：放进容量为j的背包，价值总和最大是多少。
2. 递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) ，一个是一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j]，另一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值
3. 初始化么：dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0；对于非0下标，为了有意义，需要初始化为非零值，又防止dp[j]会覆盖下一层的dp值，因此统一赋值为0即可。
4.遍历顺序：正序遍历 or 倒序遍历，正序遍历时会使得物品会被重复添加-而违背了01背包的规则（因为dp[i]是由dp[i-1]推导出来的）
与二维dp数组不同，二维数组每层数据都是独立的，但在一维dp数组时，数据的更新会利用就使用新的数据，如果使用正序则会使用更新的数值dp[i-1]去更新dp[i]；倒叙则能避免这一影响。
一维数组dp只能先遍历物品，再遍历背包；如果遍历顺序发生改变，一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。确实，尽管dp[j]的深入，dp[j-1]的数值还处于初始层的数值。

void test_1_wei_bag_problem() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;// 初始化vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
在这里插入图片描述

完全背包和01背包很大的差别体现在遍历顺序上：对于01背包——01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量；完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的。

但如果题目稍稍有点变化，就会体现在遍历顺序上。如果问装满背包有几种方式的话？那么两个for循环的先后顺序就有很大区别了，而leetcode上的题目都是这种稍有变化的类型。

最后，又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后再问，两个for循环的先后是否可以颠倒？为什么？这个简单的完全背包问题，估计就可以难住不少候选人了

// 先遍历背包，再遍历物品
void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {vector<int> dp(bagWeight + 1, 0);for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量for(int i = 0; i < weight.size(); i++) { // 遍历物品if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}
int main() {int N, V;cin >> N >> V;vector<int> weight;vector<int> value;for (int i = 0; i < N; i++) {int w;int v;cin >> w >> v;weight.push_back(w);value.push_back(v);}test_CompletePack(weight, value, V);return 0;
}

多重背包

题目链接
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
在这里插入图片描述
对于多重背包，对每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。在摊开M[i]时，比较耗时的步骤是在vector的动态底层扩容上push_back()。（其实这里也可以优化，先把所有物品数量都计算好，一起申请vector的空间。
另外一个做法是从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。和01背包还是如出一辙的。

    vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < n; i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量// 以上为01背包，然后加一个遍历个数for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}

多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了。

题目

1.斐波那契数

（题目链接）
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
1.dp数组的意义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]；
2.递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]；
3.初始化：dp[0] = 0, dp[1]=1
4.遍历顺序：从递归公式dp[i] = dp[i - 1] + dp[i - 2]；中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。
5.打印DP数据：

	// 动态规划int fib(int n) {if(n<=1) return n;int dp[2];dp[0] = 0;dp[1] = 1;for(int i=2; i<=n; i++){int cur = dp[0]+dp[1];dp[0] = dp[1];dp[1] = cur;}return dp[1];}// 递归int fib(int n) {if(n<=1) return n;return fib(n-1)+fib(n-2);}

2.爬楼梯

（题目链接）

    int climbStairs(int n) {if(n<=1) return n;int dp[2];dp[0] = 1;dp[1] = 1;for(int i=2; i<=n; i++){int cur = dp[0]+dp[1];dp[0] = dp[1];dp[1] = cur;}return dp[1];}

3.使用最小花费爬楼梯

（题目链接）
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。示例 2：输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]；输出：6；解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

    int minCostClimbingStairs(vector<int>& cost) {if(cost.size()<=1) return 0;int dp[2];dp[0] = 0;dp[1] = 0;for(int i=2; i<=cost.size(); i++){int cur = min(dp[0]+cost[i-2], dp[1]+cost[i-1]);dp[0] = dp[1];dp[1] = cur;}return dp[1];}

4.不同路径

（题目链接）
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
在这里插入图片描述
1.dp数组的意义：dp[i]的定义为
2.递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]；
3.初始化：dp[0] = 0, dp[1]=1
4.遍历顺序：从递归公式dp[i] = dp[i - 1] + dp[i - 2]；中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。

	// 动态规划法int uniquePaths(int m, int n) {std::vector<std::vector<int>> dp(m, std::vector<int>(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];}// 动态规划-改善内存int uniquePaths(int m, int n) {std::vector<int> dp(n,1);for(int i=1; i<m; i++){for(int j=1; j<n; j++){dp[j] = dp[j-1] + dp[j];}}return dp[n-1];}// 数论-分布理论-两数相乘存在溢出的情况：求组合的时候，要防止两个int相乘溢出！int uniquePaths(int m, int n) {long long res = 1;int denominator = m-1;for(int i=0; i<m-1; i++){res *= (m+n-2-i);while(denominator!=0 && res%denominator == 0){res /= denominator;denominator--;}}return res;}

5.不同路径2

（题目链接）
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
在这里插入图片描述

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid[0][0]==1) return 0;std::vector<int> dp(obstacleGrid[0].size());// 初始化第一行for(int i=0; i<dp.size(); i++){if(obstacleGrid[0][i]==1) dp[i] = 0;else if(i==0) dp[i] = 1;else dp[i] = dp[i-1];}for(int i=1; i<obstacleGrid.size(); i++){for(int j=0; j<dp.size(); j++){if(obstacleGrid[i][j]==1) dp[j]=0;else if(j!=0) dp[j] = dp[j]+dp[j-1];}}return dp.back();}