(C++/动态规划/深度讲解)LeetCode377. 组合总和 Ⅳ

这篇具有很好参考价值的文章主要介绍了(C++/动态规划/深度讲解)LeetCode377. 组合总和 Ⅳ。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划算法概述

        动态规划算法是一个分治的方法,把重叠子问题从底层到顶层拆解后,基于已经求解的子问题来求解目标问题的算法,过程清晰明了,且具有记忆化功能,在某些问题中可以避免很多重复计算,效率高,故受到很多程序员的青睐。

为什么说动态规划算法是一个从底层到顶层的算法?

        考虑斐波那契数列的算法:

#include <vector>
#include <iostream>
using namespace std;


int fib(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}


int main() {
    int result = fib(10);
    cout << result;
}

        上面的这个算法是从 n = 10 开始一步一步递归,直到 n = 1的时候停止,从终态(未知态)开始推回起始状态(已知状态),就是从顶层到底层的算法。

#include <vector>
#include <iostream>
using namespace std;
int fib(int n) {
    if (n <= 0) exit(EXIT_FAILURE);  // 防止输入无效数据
    if (n == 1) return 1;  // 特殊数据
    // 创建容器vec并进行初始化
    vector<int> vec(n + 1, 1);
    vec[0] = 0;   
    // 初始化结束

    for (int i = 2; i <= n; i++)
    {
        vec[i] = vec[i - 1] + vec[i - 2];
    }
    return vec[n];
    
}

int main() {
    int result = fib(10);
    cout << result;
}

        而这个算法是先确定所需要的数据,列表填表,从最底层的数据开始一点点的向上推导,直到达到题目所需要求的值或者找到这个问题的路径,这个就是动态规划的核心思想——分治法。

优缺点(对比普通递归算法)

        普通的递归算法就是自上而下的递归算法,动态规划对比其的优点就是列表一般都是提前规划好的,是记忆化的计算,且在数据庞杂的背景下减少了很多没有意义的风险,从而时间效率高,没有堆栈溢出的风险。缺点就是对比普通递归算法而言较复杂且很考验程序员的思维,如果填表部分没有规划好容易造成空间上的损失。

动态规划基本步骤

1.状态表示

2.写出状态转移方程

3.初始化

4.填表

5.返回值

例题详解        

        题目链接:. - 力扣(LeetCode)

        以LeetCode377. 组合总和 Ⅳ为例:

(C++/动态规划/深度讲解)LeetCode377. 组合总和 Ⅳ,算法题深度讲解,c++,动态规划,开发语言

(C++/动态规划/深度讲解)LeetCode377. 组合总和 Ⅳ,算法题深度讲解,c++,动态规划,开发语言

一般解法

        状态表示为达到某中间态的路径数,状态转移方程是nums数组中某一个数(总路径数记为1)或者某中间态(总路径数记为表中对应索引的值)的和,起始状态下,如果nums中没有元素加起来的值可以刚好等于目标值,则为0,所以我们可以把表中的值全部初始化为0,但是又要考虑当目标值为0时,已知我们初始化为0,且题目给出条件是nums中每个数都至少大于0,且为整数,所以得到nums中所有元素全部是正整数。所以接下来我们只需要分析每个中间态的路径数然后把每两个中间态相加得到下一个总路径数(例 : dp[5] = dp[2] + dp[3]),返回dp[target]即可得到最终结果。

代码如下:

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        // 初始化dp数组,当target的值为0时,因为题给条件为nums数组里面每一个数都是正数,所以可以初始化dp[0]为1
        dp[0] = 1;
        for (int i = 1; i <= target; i++)
        {
            for (int& num : nums)
            {
                if (num <= i)
                {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

        最终代码是正确的,但是中间对中间态进行求解的过程中,索引是从1开始加1,假设target是接近于INT_MAX的值,且nums是一个数据相差较大的稀疏向量呢?这就比较浪费时间和空间了,这就需要用到接下来的方法了。

进阶解法

        在上文的环境下,如果数据足够庞大或者数据够稀疏的情况下,从1开始递加1直到target会做出很多无效的操作,每次中间态的增加的量不会小于nums的最小值,所以不在这个区间的中间态是没有用的,可以省略。此时可以很轻松的想到哈希表。而C++中给出了两种哈希表的底层容器。但<unordered_map>是按照键值来排列的,大概率并不一定是添加顺序。所以为了确保确定性,需要使用map来作为容器。

代码如下:

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        map<int, int> dpTable;
        dpTable[0] = 1;  // 初始化dpTable[0] = 1

        
        // 动态规划计算,题目给出nums向量中不会有负数和0
        map<int, int>::iterator it = dpTable.begin();//前面的int是键值,后面的int是值
        while (it != dpTable.end())
        {
            for (int num : nums)
            {
                // 进行初始化,如果 num > target,则其值必为0,可以忽略
                // 所以需要判断是否满足 num <= target,其值才能为有效数值
                if (num <= target)
                {
                    // 先判断 原键值 和 num 加起来是否会爆范围,是否小于 target,再对值进行爆范围的判断。
                    // 一定要先判断是否溢出!!否则程序会报错无法运行!!
                    // 由于map的特性,没有的键会被自动创建,并且其值的值会被初始化为0
                    
                    
                    if (INT_MAX - it->first >= num && target - it->first >= num && INT_MAX - dpTable[it->first] >= dpTable[num + it->first])
                    {
                        dpTable[num + it->first] += dpTable[it->first];
                    }
                
                }

            }
            it++;
        }
        return dpTable[target];
    }
};

        本文是本系列的第一篇文章,仅作为一个浅浅的引入,后续肯定会分享更多的算法方面的题。如果大家喜欢我的文章的话,欢迎点赞收藏关注,谢谢大家!文章来源地址https://www.toymoban.com/news/detail-852670.html

到了这里,关于(C++/动态规划/深度讲解)LeetCode377. 组合总和 Ⅳ的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

    题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于:物品是否可以重复使用 思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。 对于完全背包问

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

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

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

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

    2024年04月25日
    浏览(42)
  • 【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日
    浏览(39)
  • LeetCode 377. 组合总和 Ⅳ

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

    2024年04月12日
    浏览(44)
  • 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日
    浏览(41)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(39)
  • LC377. 组合总和 Ⅳ

    代码随想录 

    2024年01月23日
    浏览(54)
  • 代碼隨想錄算法訓練營|第四十六天|完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ。刷题心得(c++)

    目录 动态规划 - 完全背包 和01背包的差別 定義 核心代碼 遍歷順序 總結 讀題 518. 零钱兑换 II 自己看到题目的第一想法 看完代码随想录之后的想法 377. 组合总和 Ⅳ 自己看到题目的第一想法 518. 零钱兑换 II - 實作 思路 Code 377. 组合总和 Ⅳ - 實作 思路 Code 總結 自己实现过

    2024年02月08日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包