当前位置: 首页 > article >正文

代码随想录算法训练营第三十七天-动态规划-完全背包-377. 组合总和 Ⅳ

  • 这是一道与上一题几乎一样的题目
  • 不同点是在上一题是组合,这道题是排列
  • 所以就要用先循环背包,内循环为物品来实现排列效果
  • 总结:
    • 对纯完全背包,求装满这个背包的最大价值,或者问能不能装满这个背包,那么两层for循环不分内外,谁在外层或内层都没有影响
    • 如果问题变为装满这个背包有多少种方法,求
  • 扩展:这道题与爬楼梯类似
    • 爬楼梯是有两种方式,一层或二层,如果有m层呢,就相当于本题集合中元素有{1, 2, 3,..., m},代表了m种爬楼梯方法(值代表一次可以爬的层数),问到达楼顶有多少种方法,这其中的楼顶层数就类似于本题中的target(万万没想到这还能联系上)
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) { // 遍历背包
            for (int j = 0; j < nums.size(); j++) { // 遍历物品
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};
  • 测试用例有两个数相加超过int的数据,所以需要在if里加上dp[i] < INT_MAX - dp[i - num]
  • 汇总

http://www.kler.cn/a/522464.html

相关文章:

  • 多级缓存(亿级并发解决方案)
  • CTF从入门到精通
  • games101-作业2
  • Unbutu虚拟机+eclipse+CDT编译调试环境搭建
  • 1.26学习
  • 大一计算机的自学总结:位运算的应用及位图
  • 使用 PyTorch 实现逻辑回归:从数据到模型保存与加载
  • 家政预约小程序11分类展示
  • 【Elasticsearch】doc_values
  • UDP/TCP ④-延时应答 || 捎带应答 || 粘包问题 || 异常处理
  • pycharm光标变成白格子 黑格子
  • 第05章 08 绘制脑部体绘制图的阈值等值面
  • Node.js 全局对象
  • web前端11--伪类与过渡
  • 循环神经网络(RNN)+pytorch实现情感分析
  • 解锁微服务:五大进阶业务场景深度剖析
  • 2025数学建模美赛|F题成品论文
  • 讯飞绘镜(ai生成视频)技术浅析(二):大模型
  • 为什么要学习rust
  • [c语言日寄]assert函数功能详解
  • 飞牛NAS新增虚拟机功能,如果使用虚拟机网卡直通安装ikuai软路由(如何解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题)
  • DeepSeek助攻!VS Code+Continue 解放双手编程!
  • DeepSeek学术写作测评第二弹:数据分析、图表解读,效果怎么样?
  • Ubuntu环境通过Ollama部署DeepSeek-R1模型教程
  • 08 比特币通用技术介绍
  • axios架构设计和原理