0/1 Knapsack DP Optimization: 2D → 1D → Range Pruning with Prefix Sum
Macros neededBasic 2DSpace Saving 1DSum Optimization
## Macros needed
### Basic 2D 
```C++
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        // 每个num只能选一次并且使和恰好为target
        // 0/1 knapsack
        // dp[i][j] : 在前i个num中选，使得 sum == j 的最长子串长度
        // dp[0][0] = 0;
        // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + 1);
        // return dp[n][target]
        int n = nums.size();
        vvi dp(n + 1, vi(target + 1, -1));
        dp[0][0] = 0;
        fori(1, n + 1)
        {
            forj(0, target + 1)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1] && (dp[i - 1][j - nums[i - 1]] >= 0))
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i - 1]] + 1);
            }
        }
        return dp[n][target];
}
```
### Space Saving 1D
```C++
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        vi dp(target + 1, -1);
        dp[0] = 0;
        fori(1, n + 1)
        {
            fordj(target, nums[i - 1])
            {
                if(dp[j - nums[i - 1]] >= 0)
                    dp[j] = max(dp[j], dp[j - nums[i - 1]] + 1);
            }
        }
        return dp[target];
}
```

### Sum Optimization
```C++
class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        vi dp(target + 1, -1);
        dp[0] = 0;
        int sum = 0;
        for(auto x : nums)
        {
            sum += x;
            fordj(min(sum, target), x)
            {
                if(dp[j - x] >= 0)
                    dp[j] = max(dp[j], dp[j -x] + 1);
            }
        }
        return dp[target];
    }
};
```
['Dynamic Programming', 'C++']