专栏首页Michael阿明学习之路LeetCode 377. 组合总和 Ⅳ(DP)

LeetCode 377. 组合总和 Ⅳ(DP)

1. 题目

给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意,顺序不同的序列被视作不同的组合。 因此输出为 7。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum-iv

2. DP解题

类似于爬楼梯问题的变种

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 563. 背包问题 V(DP)

    给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。

    Michael阿明
  • LeetCode 63. 不同路径 II(DP)

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    Michael阿明
  • LeetCode 1155. 掷骰子的N种方法(DP)

    Michael阿明
  • 【leetcode刷题】T170-组合总和 Ⅳ

    https://leetcode-cn.com/problems/combination-sum-iv/

    木又AI帮
  • Golang Leetcode 377. Combination Sum IV.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89089210

    anakinsun
  • LintCode 563. 背包问题 V(DP)

    给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。

    Michael阿明
  • 打卡群刷题总结1001——组合总和 Ⅳ

    链接:https://leetcode-cn.com/problems/combination-sum-iv

    木又AI帮
  • Leetcode-Medium 416. Partition Equal Subset Sum

    给定仅包含正整数的非空数组,查找是否可以将数组划分为两个子集,使得两个子集中的元素总和相等。 例子1:

    致Great
  • 【leetcode刷题】T171-分割等和子集

    https://leetcode-cn.com/problems/partition-equal-subset-sum/

    木又AI帮
  • 《剑指offer》第26天:最大子序和

    首先我们分析题目,一个连续子数组一定要以一个数作为结尾,那么我们可以将状态定义成如下:

    程序员小浩

扫码关注云+社区

领取腾讯云代金券