3.动态规划.题目1

  • 开发
  • 22

3.动态规划.题目1

题目

6.正数拆分

（题目链接）
给定一个正整数 n ，将其拆分为 k 个 正整数 的和==（ k >= 2 ），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 ==。

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]，那么遍历的顺序一定是从前到后遍历的。
使用for循环i从2~n开始遍历，得到dp数组，dp[i]定义为对应数值i拆分得到的最大乘积，那dp[i]是如何得到的呢，是从1.两数差分的乘积最大值——j*(i-j)，2.多数拆分的最大值——j*dp[i-j] 得到的（这里j不用dp拆分，一方面是因为这样的话就会强制让n拆分成4份数值；另一方面对于j的拆分，可以体现在dp[i-j]中，保留一个不拆分的数值的意义）。
因此dp[i]是从dp[i-1]得到的。又因为若是拆成两数，想得到最大乘积，尽量让两数接近，所以优化方式是(j<i/2)。

    int integerBreak(int n) {
        std::vector<int> 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];
    }

7.不同的二叉树

（题目链接）
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
在这里插入图片描述
思考到这里，这道题目就有眉目了，这个规律很重要！。dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量；元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 x 左子树有0个元素的搜索树数量；元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 x 左子树有1个元素的搜索树数量；元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 x 左子树有2个元素的搜索树数量
动态规划思路：
1.dp数组的意义：dp[i]的定义为1到i为节点组成的二叉搜索树的个数；
2.递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
3.初始化：只需要初始化dp[0]就可以了，推导的基础，都是dp[0]，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
4.遍历顺序：从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。

    int numTrees(int n) {
        std::vector<int> dp(n+1);
        dp[0]=1;
        for(int i=1; i<=n; i++){
            for(int j=0; j<i; j++) dp[i] += dp[j]*dp[i-j-1];
        }
        return dp.back();
    }

8.分割等和子集

（题目链接）
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。提示：1 <= nums.length <= 200；1 <= nums[i] <= 100
暴力解法：使用回溯算法 采用时间复杂度为O(2^n)去采取每种可能；
动态规划：抽象为找到集合里能够出现 sum / 2 的子集总和，元素我们只能用一次，所以使用的是01背包。本题里面每个数值即是重量，也是价值。
1.dp数组定义：容量为j的背包，所背的物品价值最大可以为dp[j]；
2.递归关系：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) 一维dp数组的写法；
3.初始化：从dp[j]的定义来看，首先dp[0]一定是0；非0下标，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
4.遍历顺序

    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i:nums) sum += i;
        if(sum%2==1) return false;
        int target = sum/2;
        std::vector<int> dp(10001, 0);
		// 外层物品遍历nums[i]
        for(int i=0; i<nums.size(); i++){
        	//内层背包容量从target减至nums[i]遍历
            for(int j=target; j>=nums[i]; j--){
                dp[j]=max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target) return true;
        return false;
    }

9.最后一块石头重量2

（题目链接）
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
提示：1 <= stones.length <= 30； 1 <= stones[i] <= 100

题目的意思是将数组里的数字两两相消，保留其差值，最后剩余一个值。要返回该差值的最小值，即是理解为那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]，这两堆数值相消，这就类似8.题分割等子集，但不同的是计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的，允许存在差值的情况。

    int lastStoneWeightII(vector<int>& stones) {
        std::vector<int> dp(15001, 0);
        int sum=0;
        for(int i:stones) sum += i;
        int target = sum/2;
        for(int i=0; i<stones.size(); i++){
            for(int j=target; j>=stones[i]; j--){
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[target]-dp[target];
    }

10.目标和

（题目链接）
给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
给定数组并且为每个数值赋予符号+，-，其实意味着将数值分为两组x，sum-x，假设x-(sum-x)=target，则x=(sum+target)/2，若不能整除，这说明该数组无论如何符号组合，都不可能凑出target。因此该问题也就被转化为了从数组中选择x数组，使其和为(sum+target)/2即可。
暴力解法：回溯法——通过backtracking函数递归数组中和数值选择组合。
动态规划：01背包问题。

    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int n:nums) sum += n;
        if(abs(target)>sum) return 0;
        if((target+sum)%2==1) return 0;
        
        int bagSize = (target + sum) / 2;
        std::vector<int> dp(bagSize+1, 0);
        dp[0]=1;
        for(int i=0; i<nums.size(); i++){
            for(int j=bagSize; j>=nums[i]; j--){
                dp[j] += dp[j-nums[i]]; 
            }
        }
        return dp[bagSize];
    }

11.一和零

（题目链接）
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
本题中strs 数组里的元素就是物品，每个物品都是一个！而m 和 n相当于是一个背包，两个维度的背包。
在这里插入图片描述
1.dp数组定义：dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.递归关系：可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。
3.初始化：因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖
4.遍历顺序：01背包为什么一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

    int findMaxForm(vector<string>& strs, int m, int n) {
        std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, 0));
        for(std::string str:strs){
            int onesnum = 0;
            int zeronum = 0;
            for(char c:str){
                if(c=='1') onesnum++;
                else zeronum++;
            }

            for(int i=m; i>=zeronum; i--){
                for(int j=n; j>=onesnum; j--){
                    dp[i][j] = max(dp[i][j], dp[i-zeronum][j-onesnum]+1);
                }
            }
        }
        return dp[m][n];
    }

12.零钱兑换2

（题目链接）
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数！
1.dp数组以及下标的含：凑成总金额j的货币组合数
2.递推关系：dp[j] += dp[j - coins[i]]，将所有j下对coins[i]的情况相加——这与01背包的目标和这道题目类似的道理
3.初始化：dp[0]一定要为1，dp[0] = 1是 递归公式的基础
4.遍历顺序：纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！但这题目是求形成j的组合数，若是1）外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况，这种遍历顺序中dp[j]里计算的是组合数，因为在背包重量j情况下，物品i放入顺序固定了；2）把两个for交换顺序，此时dp[j]里算出来的就是排列数！，此时物品的顺序是杂乱的。
在这里插入图片描述

    int change(int amount, vector<int>& coins) {
        std::vector<int> dp(amount+1, 0);
        dp[0]=1;
        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount; j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }

时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度；空间复杂度: O(m)
本题的递推公式，其实我们在494. 目标和 (opens new window)中就已经讲过了，而难点在于遍历顺序！在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品

13.组合总和4

（题目链接）
给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。请注意，顺序不同的序列被视作不同的组合！
1.dp[i]: 凑成目标正整数为i的排列个数为dp[i]；
2.递推关系：dp[i]（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来，dp[i] += dp[i - nums[j]]。
3.初始化：dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础；
4.遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
在这里插入图片描述

    int combinationSum4(vector<int>& nums, int target) {
        std::vector<int> dp(target+1, 0);
        dp[0] = 1;
        for(int j=0; j<=target; j++){
            for(int i=0; i<nums.size(); i++){
            	// C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]
                if(j-nums[i]>=0 && dp[j]<INT_MAX-dp[j-nums[i]]) {
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];

时间复杂度: O(target * n)，其中 n 为 nums 的长度；空间复杂度: O(target)

14.爬楼梯-进阶版

（题目链接）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
在2.爬楼梯中 只是讲了一下爬楼梯最直接的动规方法（斐波那契），2.中只能至多爬两个台阶，这次你可以至多m (1 <= m < n)个台阶，问有多少种不同的方法到达楼顶。
这题可以抽象理解为完全背包问题，步数以及每步的台阶数没有限制。
1.dp[i]数组定义：爬到有i个台阶的楼顶，有dp[i]种方法
2.递推关系：dp[i] += dp[i - j]，j为一步台阶数
3.初始化：dp[0] 一定为1，dp[0]是递归中一切数值的基础所在
4.遍历顺序：这题每步的台阶数是无序的，因此是个有序组合-排列问题，因此遍历的外层是所到达的台阶数i，内层是上一步台阶数j。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++) { // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        cout << dp[n] << endl;
    }
}

15.零钱兑换

（题目链接）
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
1.dp[i]数组定义：凑足总额为j所需钱币的最少个数为dp[j]
2.递推关系：凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]），所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的，因此有dp[j] = min(dp[j - coins[i]] + 1, dp[j])；
3.初始化：0下标——凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0；非0下标考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖，所以下标非0的元素都是应该是最大值。
4.遍历顺序：本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数

    int coinChange(vector<int>& coins, int amount) {
        std::vector<int> dp(amount+1, INT_MAX);
        dp[0]=0;
        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount; j++){
                if(dp[j-coins[i]]==INT_MAX) continue; // 跳过dp还是初始值的情况
                dp[j] = min(dp[j], dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==INT_MAX) return -1;
        return dp[amount];
    }

时间复杂度: O(n * amount)，其中 n 为 coins 的长度；空间复杂度: O(amount)

16.完全平方数

（题目链接）
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
1.dp[j]数组定义：和为j的完全平方数的最少数量为dp[j]；
2.递推关系：dp[j] 可以由dp[j - i ^2]推出， dp[j - i^2] + 1 便可以凑成dp[j]，因此递推关系式是dp[j] = min(dp[j - i * i] + 1, dp[j])
3.初始化：dp[0]=0完全是为了递推公式；非0下标时——递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值。
4.遍历顺序：所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的
这题理解好题意后，就是与15.零钱兑换类似，知识在递推关系的时候有点差别。

    int numSquares(int n) {
        std::vector<int> dp(n+1, INT_MAX);
        dp[0]=0;
        for(int i=0; i<=n; i++){
            for(int j=1; j*j<=i; j++){
                dp[i] = min(dp[i-j*j]+1, dp[i]);
            }
        }
        return dp[n];
    }

时间复杂度: O(n * √n)；空间复杂度: O(n)

背包问题总结

求装满背包有几种方法，递归公式都是一样的，没有什么差别，但关键在于遍历顺序！
本题与动态规划：12.零钱兑换2就是一个鲜明的对比，一个是求排列，一个是求组合，遍历顺序完全不同

  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

背包的递推公式

  1. 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    题目：分割等和子集，最后一块石头的重量
  2. 问装满背包有几种方法：dp[j] += dp[j - nums[i]]
    题目：目标和，零钱兑换，组合总和4，爬楼梯进阶版-完全背包
  3. 问背包的装完的最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    题目：一和零
  4. 问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
    题目：零钱兑换，完全平方数

遍历顺序

  • 01背包：二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历；一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
  • 完全背包：纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。题目稍有变化，两个for循环的先后顺序就不一样了，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。

对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了

阅读全部

相关推荐

  3. 动态规划入门题目

    2024-07-13 11:10:05       59 阅读

  7. 【LeetCode】动态规划--题目练习

    2024-07-13 11:10:05       38 阅读

  10. 区间价值 --- 题解--动态规划

    2024-07-13 11:10:05       57 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-13 11:10:05       66 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-13 11:10:05       70 阅读

  9. 在Django里面运行非项目文件

    2024-07-13 11:10:05       57 阅读

  19. Python语言-面向对象

    2024-07-13 11:10:05       68 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-13 11:10:05       62 阅读

热门阅读

  2. 什么是B树及其变种B+树

    2024-07-13 11:10:05       22 阅读

  8. c#视觉应用开发中如何在C#中进行视频帧差分？

    2024-07-13 11:10:05       17 阅读

  10. 二叉搜索树刷题

    2024-07-13 11:10:05       21 阅读

  11. Python实现音频均衡和降噪

    2024-07-13 11:10:05       20 阅读

  17. 深度学习之轻量化神经网络MobileNet

    2024-07-13 11:10:05       22 阅读

  18. 基于深度学习的RGB图像和IMU的数据融合

    2024-07-13 11:10:05       21 阅读

  20. F12打不开、打开后页面跳转、控制台持续刷新

    2024-07-13 11:10:05       20 阅读

  22. SQL注入：基于错误

    2024-07-13 11:10:05       20 阅读

  24. Python高级（四）_内存管理

    2024-07-13 11:10:05       26 阅读

  27. 菜单（Menu）

    2024-07-13 11:10:05       20 阅读

  29. QAbstractButton

    2024-07-13 11:10:05       20 阅读