【随想录学习】——第十章 动态规划（0-1背包+完全背包）

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

509. 斐波那契数

推导：

1. dp数组表示斐波那契数列，dp[i]表示i处的数字值
2. 由于斐波那契数列的性质，dp[i]=dp[i-1]+dp[i-2]

方法一：维护大小为N的数组

class Solution {
public:
    int fib(int n) {
        vector<int> dp(n + 1);
        if(n<=1){
            return n;
        }
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

方法二：维护大小为2的数组，减少空间复杂度

class Solution {
public:
    int fib(int n) {
        //vector<int> dp(2);
        int dp[2];
        if(n<=1){
            return n;
        }
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            int sum=dp[0]+dp[1];
            dp[0]=dp[1];
            dp[1]=sum;
        }
        return dp[1];
    }
};

注意，在该方法中，将数组设置为int而不是vector向量的形式，是因为vector更适用于动态大小的情况，int[]适用于固定大小的情况

70. 爬楼梯

推导：

1. dp[i]： 爬到第i层楼梯，有dp[i]种方法
2. 首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

1. 初始化中，纠结dp[0]的值，但是题目中n>1，所以没有必要考虑，直接初始化dp[1]=1
2. 整体其实就是斐波那契数列

class Solution {
public:
    int climbStairs(int n) {
        //必须定义为dp[3]，因为dp[3]=dp[0],dp[1],dp[2]
        int dp[3];
        if(n<=1){
            return n;
        }
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            int sum=dp[1]+dp[2];
            dp[1]=dp[2];
            dp[2]=sum;
        }
        return dp[2];
    }
};

746. 使用最小花费爬楼梯

1. dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
2. 可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

1. 新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。

所以初始化 dp[0] = 0，dp[1] = 0;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        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. 不同路径

深搜

这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。

注意题目中说机器人每次只能向下或者向右移动一步，所以每一步就是两种选择，分叉成两个节点，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！

问题就可以转化为求二叉树叶子节点的个数，

但是使用该方法的话会超时，因为需要遍历整棵树

动态规划

1. dp[i][j]表示走到（i,j）的路径数量
2. 因为dp[i][j]只可能从dp[i-1][j]和dp[i][j-1]即（i-1,j）和（i,j-1）走来，且从这两个点到（i,j）也就是一步之遥，所以dp[i][j]=dp[i-1][j]+dp[i][j-1]
3. 初始化：镶边部分即dp[i][0]和dp[0][j]的由于只能向左走和向右走，因此全部初始化为1

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        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. 不同路径Ⅱ

与上一题相比就是多了障碍物的存在

62.不同路径 (opens new window)中我们已经详细分析了没有障碍的情况，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。

即如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。dp[0][j]同理

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();//宽
        int n=obstacleGrid[0].size();//高
        vector<vector<int>> dp(m, vector<int>(n));
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1){
            return 0;
        }
        //给横向赋值为1.但是障碍之后都不赋值了，因为根本到不了
        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]==0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
                else{
                    dp[i][j]=0;
                }
            }
        }
        return dp[m-1][n-1];
    }
};

这一题我一直死在数组的定义上

就是要用.size()去获取行数和列数，sizeof()得到的是字节大小

343. 整数拆分

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

初始化从2开始才有意义

因为如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了，所以需要同时比较(i-j)*j和dp[i - j] * j，即考虑到拆分了两个数的情况。

dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
                //之所以要带上dp[i]是因为在j的循环过程中i是不变的，所以dp[i]会实时更新，下面的写法就是错的
                //dp[i]=max(dp[i-j]*j,(i-j)*j);
            }
        }
        return dp[n];
    }
};

96. 不同的二叉搜索树

举例，假设n=3

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

这个图特别清楚，就是左右的大小关系都有了

dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当于是头结点的元素，从1遍历到i为止。

所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。所以dp[0]初始化为1，且之后相乘总不能让结果为0

0-1背包理论基础

1. dp数组确认

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 递推公式确认

可以有两个方向推出来dp[i][j]，

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
• 放物品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. 初始化

1. 背包容量为0时价值一定为0

当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

4. 遍历顺序

先遍历 物品还是先遍历背包重量呢？

其实都可以！！ 但是先遍历物品更好理解

0-1背包基础（2）

1. 确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

1. 一维dp数组的递推公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

1. 初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

1. 遍历顺序

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

那么问题又来了，为什么二维dp数组遍历的时候不用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

416. 分割等和子集

一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包

本题元素只能使用一次，故使用01背包

本题的重量和价值相同

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j

使用的是滚动数组，初始化大小均为0

首先将数组元素累加起来得到sum，如果sum为奇数，则不可能分成两份，否则的话就让target=sum

1049. 最后一块石头的重量Ⅱ

尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了

所以和上一题几乎是一模一样的

dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。

dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。

因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000

而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

全部初始化为0即可

494. 目标和

本题要如何使表达式结果为target，

假设加法集合称为plus，减法集合称为minus

既然为target，那么就一定有 plus组合 - minus组合 = target。

plus+ minus = sum，而sum是固定的。plus = sum - minus

此时问题就是在集合nums中找出和为plus的组合。

当然整除不了的话就说明找不到对应的方法

dp[j]定义

dp[j]表示装满容量为j的背包有dp[j]种方法

dp[j]推导

dp[j]的推导通过dp[j-nums[i]]来

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

为什么一直是容量为5？因为j不变变的是i，所以容量不变

都是凑成容量为5，所以最终dp[j]=所有相加

dp[j] += dp[j - nums[i]]

dp[j]初始化

dp[0]必须为1，否则结果全部为0

474. 一和零

依旧是01背包问题，虽然有m和n两个维度，但是每个元素还是只能使用一次

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

1. 确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

1. dp数组如何初始化

全部初始化为0

1. 遍历顺序

逆序遍历，保证每个数字只被使用一次

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(string str: strs){
            //按照字符串进行遍历统计
            int zeroNum=0;
            int oneNum=0;
            //统计字符
            for(char c: str){
                if(c=='0'){
                    zeroNum++;
                }
                else{
                    oneNum++;
                }
            }
            //遍历顺序已经无所谓了，因为是两个维度
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    //减掉的是weight，加上的是value
                    dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
};

完全背包理论基础

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

属于是横向更新，01背包中我们是层级更新

518. 零钱兑换Ⅱ

一看到钱币数量不限，就知道这是一个完全背包

本题的物品是钱币，背包是金额总和

求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]]，和目标和那一题一样

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

本题说明的是兑换的方法一共多少种，无关顺序，221和212是一样的，因此求的是组合数而不是排列数，因此先遍历背包再遍历物品

先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。因此不会有重复

377. 组合总和Ⅳ

和上一题的区别就是，本题求的是排列数，所以先背包后物品

为了不让数组越界记得判断j-nums[i]>0

C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。

70. 爬楼梯进阶版

之前做的 爬楼梯 是只能至多爬两个台阶

所以其实就是一个斐波那契数列

但是本题每次爬楼梯的个数不限制，所以是一个背包问题

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题

和上一题基本就是一道题了。

322.零钱兑换

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

所以本题并不强调集合是组合还是排列。

初始化全部为INT_MAX，这样min函数才能起作用

而dp[0]=0！！！这个很重要

一开始我设置为1，因为我担心会像前面几题一样，导致最后dp永远为0

但是前面的题的递推公式是dp+=dp[j-nums[i]]这样的

本题存在+1，故无所谓

279. 完全平方数

和上一题一模一样 略过文章来源地址https://www.toymoban.com/news/detail-806392.html

到了这里，关于【随想录学习】——第十章 动态规划（0-1背包+完全背包）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！