10-17-2026 继续刷题打卡

今天复习动态规划，真的好几年没有写过动态规划的题目了，脑袋仿佛生锈了一样，状态转移的方程很难想。

• dp[j] : 对于已经考虑过的数字，能否凑出目标数j. 
• 需要注意在更新dp array的时候需要倒序更新，避免重复选择当前数字。
• dp[j] = dp[j] || dp[j - nums[i]]

• Partition Equal Subset Sum

1. class Solution { public: bool canPartition(vector& nums) { int n = nums.size(); int sum = 0; for (int i = 0; i < n; i++) { sum += nums[i]; }
3.     if (sum % 2) {
4.         return false;
5.     }
6.     int target = sum / 2;
7.     vector<bool> dp(target + 1, false);
8.     dp[0] = true;
9.     for (int& num : nums) {
10.         for (int i = target; i >= 0; i--) {
11.             if (dp[i] && i + num <= target) {
12.                 dp[i+num] = true;
13.             }
14.         }
15.     }
16.     return dp[target];
17. }
19. };

复制代码

0/1 背包问题