背包问题

背包问题总结

知识要点1

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包

        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int i=0; i<nums.size(); ++i) {
            for (int j=nums[i]; j<=target; ++j) {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];

• 如果求排列数就是外层for遍历背包，内层for循环遍历物品

        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int j=1; j<=target; ++j) {
            for (int i=0; i<nums.size(); ++i) {
                if (j >= nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];

知识要点2

• 01背包内层循环从大到小
• 完全背包内层循环从小到大

知识要点3

• 组合问题公式：dp[i] += dp[i-num]
• True、False问题公式：dp[i] = dp[i] or dp[i-num]
• 最大最小问题公式：dp[i] = min(dp[i], dp[i-num]+1) 或者 dp[i] = max(dp[i], dp[i-num]+1)