【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析

这篇具有很好参考价值的文章主要介绍了【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划

动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

879. 盈利计划 - 力扣(LeetCode)

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

题目解析

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

状态表示

这个问题本质上是,

  1. 挑选出一些工作作为一个集合,这个集合满足某些要求,解决某些问题。而背包问题就是挑选出一些物品作为一个集合,这个集合满足某些要求,解决某些问题。

  2. 挑选出来的工作不可以无限选取,所以属于二维01背包问题。

背包问题的状态表示是,

定义dp[i][j]表示从前i个物品中挑选,总体积不超过j,所有选法中,所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选,总体积恰好为j,所有选法中,所能达到的最大价值。

我们根据背包问题的状态表示,定义出该问题的状态表示。

因此我们可以定义,dp[i][j][k]表示,从前i个工作中挑选,总需人数不超过j,总利润不少于k,总盈利计划个数。

状态转移方程

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

状态转移方程通常都是根据最后一个位置的具体状况进行分类讨论。

  1. 如果不选择第i个工作, 此时只能从前i-1个工作中挑选出集合,此时dp[i][j][k]=dp[i-1][j][k]。

  2. 如果选择第i个工作, 此时第i个工作需要的人数为group[i-1],产生的利润为profit[i-1],本来总人数不能超过j,选取第i个工作后,总人数不能超过j-group[i-1],本来总利润需要不少于k,选取第i个工作后,总利润需要不少于k-profit[i-1],因此dp[i][j][k]=dp[i-1][j-group[i-1]][k-profit[i-1]]。表示在前i-1个工作中挑选集合的集合个数,每一个集合都加入第i个工作,此时的集合个数为dp[i][j][k]。此时还需要判断j-guoup[i-1],k-profit[i-1]是否小于0,的情况。小于0就越界了。

    1. 如果j-group[i-1]<0, 表示第i个工作需要的人数就大于了j,此时dp[i][j][k]=0。

    2. 如果j-group[i-1]>=0, 说明此时可以完成第i个工作,dp[i][j][k]=dp[i-1][j-group[i-1][k-profit[i-1]],还需要考虑k-profit[i-1]的正负性。

      1. 如果k-profit[i-1]<0, 表示第i个工作产生的利润就可以满足最低需求利润,所以再从前面工作中挑选,不需要考虑它的利润条件,即产生的利润大于等于0即可。此时dp[i][j][k]=dp[i-1][j-group[i-1]][0]。

      2. 如果k-profit[i-1]>=0, 此时dp[i][j][k]=dp[i-1][j-group[i-1]][k-profit[i-1]]。

综上所述,将上述情况进行合并和简化,得到状态转移方程为,

 
        dp[i][j][k] = dp[i - 1][j][k];
        if (j - group[i - 1] >= 0)
            dp[i][j][k] = (dp[i][j][k]+dp[i - 1][j - group[i - 1]]
                             [max(0, k - profit[i - 1])])%MOD;

MOD=1e9+7,因为题目说得到的数可能很大,需要对MOD取余,所以两个数每相加,就对MOD取余。

初始化

根据状态转移方程,我们知道,推导(i,j,k)位置的状态需要用到(i-1,j,k)位置的状态,if判断保证j-group[i-1]一定不会小于0,dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])],所以这个状态中只需要考虑(i-1)。所以我们需要初始化第一行,推导第一行的时候会发生越界的情况,此时没有前驱状态。

i==0,表示不选工作,人数不超过j,集合利润不少于k,集合个数,此时只有dp[0][j][0]=1,其他都为0。

故初始化为,

 
        for (int j = 0; j <= n; j++) {
            dp[0][j][0] = 1;
        }

填表顺序

根据状态转移方程,我们在推导(i,j,k)位置的状态时,需要用到(i-1,j,k)(i-1,j-group[i-1],k-profit[i-1])位置的状态。这些状态不会越界,初始化保证了他们不会越界。

  1. 固定i, i需要从小到大变化,当推导(i,j,k)位置状态时,(i-1,,)位置状态已经得到,所以j,k的变化可以从小到大,也可以从大到小。

  2. 固定j, j的变化需要从小到大,又因为需要用到(i-1,j,k)位置的状态,所以i的变化需要从小到大,此时k的变化可以从小到大也可以从大到小。

  3. 固定k, k的变化需要从小到大,又因为需要用到(i-1, j,k)位置的状态,所以i的变化需要从小到大,此时j的变化可以从小到大,也可以从大到小。

返回值

状态表示为dp[i][j][k]表示,从前i个工作中挑选,总需人数不超过j,总利润不少于k,总盈利计划个数。

结合题目意思,我们需要在前m个工作中挑选,总需人数不超过n,总利润不少于minProfit,总盈利计划个数。

返回dp[m][n][minProfit]

(m表示工作个数)

代码实现

 
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group,
                          vector<int>& profit) {
        int m = group.size();
        int MOD = 1e9 + 7;
        vector<vector<vector<int>>> dp(
            m + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));

        for (int j = 0; j <= n; j++) {
            dp[0][j][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j - group[i - 1] >= 0)
                        dp[i][j][k] = (dp[i][j][k]+dp[i - 1][j - group[i - 1]]
                                         [max(0, k - profit[i - 1])])%MOD;
                }
            }
        }
        return dp[m][n][minProfit];
    }
};

377. 组合总和 Ⅳ - 力扣(LeetCode)

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

题目解析

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

因此我们应该换一种思路,尝试正向解决这道问题。

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

在正向推导过程我们发现了重复子问题,求元素和为target一共有多少种排列方法数,等价于求元素和为target-第一个位置上的元素值,一共有多少种排列方法数,然后再考虑第一个位置上所有情况即可。

因此我们可以定义状态表示为dp[i]元素和为i的所有排列方法数。

状态表示

定义dp[i]元素和为i的所有排列方法数。

状态转移方程

  1. 如果有排列,

    1. 第一个位置为nums[0], 此时dp[i]=dp[i-nums[0]]。

    2. 第一个位置为nums[1], 此时dp[i]=dp[i-nums[1]]。

    3. 第一个位置为nums[2], 此时dp[i]=dp[i-nums[2]]。

    4. .......

  2. 如果没排列, dp[0]=1。

综上所述,状态转移方程为,dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+..........

如果i-nums[0]<0,此时不存在。同时dp[0]=1。

 
            for(auto j:nums){
                if(j<=i){
                    dp[i]+=dp[i-j];
                }
            }

初始化

根据状态转移方程,dp[i]+=,所以每个位置都需要初始化为0。而没有排列的时候,dp[0]=1。

填表顺序

根据状态转移方程,推导i位置状态需要用到i-j位置的状态,所以i的变化需要从小到大。

返回值

状态表示为,定义dp[i]元素和为i的所有排列方法数。

结合题目意思,我们需要返回dp[target]

代码实现

 
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<double>dp(target+1);
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(auto j:nums){
                if(j<=i){
                    dp[i]+=dp[i-j];
                }
            }
        }
        return dp[target];
    }
};

96. 不同的二叉搜索树 - 力扣(LeetCode)

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

题目解析

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析,动态规划,c++,算法,动态规划

状态表示

定义dp[i]表示节点数为i,组成的二叉搜索树种类数。

状态转移方程

  1. 当节点数至少为3时,假设j作为根节点。 此时左边是1~(j-1),一共有(j-1)-1+1=j-1 个数, 右边是(j+1)~i,一共有i-(j+1)+1=i-j 个数,

      状态转移方程为,

     
    for(int j=1;j<=i;j++){
            dp[i]+=dp[j-1]*dp[i-j];
        }
  2. 当节点数为2时, dp[2]=2。

  3. 当节点数为1时, dp[1]=1。

  4. 当节点数为0时, dp[0]=1。此时表示没有节点,二叉搜索树的种类数,空也算是一种。表示左孩子为0时,种类数为右孩子种类数乘以1,或者右孩子为0时,种类数为左孩子种类数乘以1。

初始化

根据状态转移方程,dp[i]+=,所以每个状态先初始化为0。

填表顺序

根据状态转移方程,推导i位置状态时需要用到j-1,和i-j位置的状态,所以i的变化需要从小到大。

返回值

状态表示为,定义dp[i]表示节点数为i,组成的二叉搜索树种类数。

结合题目意思,我们需要返回dp[n]

代码实现

 
class Solution {
public:
    int numTrees(int n) {
        vector<int>dp(n+1);
        if(n==0||n==1) return 1;
        else if(n==2) return 2;
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
        
    }
};

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!文章来源地址https://www.toymoban.com/news/detail-794428.html

到了这里,关于【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ,三道题目深度解析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。 动规五步曲来分

    2024年02月01日
    浏览(52)
  • 代码随想录第44天|动态规划:完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

    代码随想录 (programmercarl.com) 动态规划之完全背包,装满背包有多少种方法?组合与排列有讲究!| LeetCode:518.零钱兑换II_哔哩哔哩_bilibili 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。 完全背包中的物品可以添加多次,所以要从小到大遍历: 518. 零钱兑换

    2024年04月25日
    浏览(42)
  • 【LeetCode题目详解】第九章 动态规划part06 完全背的讲解 518. 零钱兑换 II 377. 组合总和 Ⅳ (day44补)

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

    2024年02月09日
    浏览(35)
  • 【Leetcode】377. 组合总和 Ⅳ

    题目链接🔗 给你一个由 不同 整数组成的数组 n u m s nums n u m s ,和一个目标整数 t a r g e t target t a r g e t 。请你从 n u m s nums n u m s 中找出并返回总和为 t a r g e t target t a r g e t 的元素组合的个数。 题目数据保证答案符合 32 32 32 位整数范围。 示例 1: **输入:**nums = [1,2,3],

    2024年04月23日
    浏览(38)
  • LeetCode 377. 组合总和 Ⅳ

    解题思路 之前一直以为这是背包问题,后来发现,这个是有顺序的, 而背包问题是无序的,但是我们也可以用dp分析法来分析。 相关代码

    2024年04月12日
    浏览(43)
  • LC377. 组合总和 Ⅳ

    代码随想录 

    2024年01月23日
    浏览(52)
  • 377. 组合总和 Ⅳ 70.魔改爬楼梯

    题目: 给一个正整数数组和一个正整数目标值,数组的每个元素可取无限次,求总额达到目标值的最大排列数。  dp[j]含义: dp[j]:达到目标值j的整数组合数为dp[j] 递推公式: 求装满背包有几种方法(组合,排列数)用:dp[j] += dp[j - nums[i]]; 初始化: dp[0]=1 遍历顺序: 先物品

    2024年02月08日
    浏览(38)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(40)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(41)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II--求组合、组合总和IV--求排列)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包