专栏首页Michael阿明学习之路LintCode 563. 背包问题 V(DP)

LintCode 563. 背包问题 V(DP)

1. 题目

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

每一个物品只能使用一次

样例
给出候选物品集合 [1,2,3,3,7] 以及 target 7
结果的集合为:
[7]
[1,3,3]
返回 2

2. 解题

  • dp[i][j]dp[i][j]dp[i][j] 表示第 i 个物品下,重量为 j 的方案数
class Solution {
public:
    int backPackV(vector<int> &nums, int target) {
        if(nums.size() == 0)
            return 0;
        if(target == 0)
            return 1;
        int n = nums.size(), i, j;
        vector<vector<int>> dp(n,vector<int>(target+1, 0));
        dp[0][0] = 1;//第一个物品不放
        if(nums[0] <= target)
            dp[0][nums[0]] = 1;//第一个物品放,1种方案
        for(i = 1; i < n; i++)//遍历剩余的物品
        {
            for(j = 0; j <= target; j++)
            {
                if(dp[i-1][j] != 0)//上一行所有存在的状态
                {
                    dp[i][j] += dp[i-1][j];//i个物品不放
                    if(j <= target-nums[i])//i个物品放进去不超重
                        dp[i][j+nums[i]] += dp[i-1][j];
                }
            }
        }
        return dp[n-1][target];
    }
};
  • 当前行状态只依赖于上一行,可以进行状态压缩,节省存储空间,代码略。

100% 数据通过测试 总耗时 201 ms 您的提交打败了 45.80% 的提交!

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 377. 组合总和 Ⅳ(DP)

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

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

    Michael阿明
  • LeetCode 44. 通配符匹配(DP)

    给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。

    Michael阿明
  • Golang Leetcode 377. Combination Sum IV.go

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

    anakinsun
  • 【leetcode刷题】T170-组合总和 Ⅳ

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

    木又AI帮
  • LeetCode 377. 组合总和 Ⅳ(DP)

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

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

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

    木又AI帮
  • 剑指offer--跳台阶

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    AI那点小事
  • 剑指offer--矩形覆盖

    题目描述 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

    AI那点小事
  • LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target(动态规划)

    题解:动态规划 dp[i]表示从0到i的子数组的答案。维护前缀数组sums[],我们维护一个记录前缀和的map,map[x]表示前缀和是x距离当前i最近的下标。

    ShenduCC

扫码关注云+社区

领取腾讯云代金券