Both knapsack problems and combination counting problems follow a similar pattern in dynamic programming. Each element in a sequence has two states: selected or not selected. The current state can be derived from the previous state based on these two choices.

DP Array Definition

The definition of the dp array depends on the problem requirements. For knapsack problems seeking maximum value under a weight constraint, define dp[i][j] as the maximum value obtainable from the first i items when the knapsack capacity is j. For combination counting problems where we need to count combinations satisfying a specific condition (such as achieving a target sum), define dp[i][j] as the number of ways to achieve sum j using the first i elements.

Initialization Strategy

The dp array dimensions are typically dp[size+1][limit+1], where size represents the sequence length and limit is determined by the constraint. In knapsack problems, limit represents the capacity; in combination problems, limit represents the target sum.

For most cases, initialization starts with all zeros since choosing nothing yields zero value or zero ways. However, when the current state depends on accumulating from previous states, dp[0][0] must be set to 1. For example, in combination sum problems with the recurrence dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]], the base case dp[0][0] = 1 is essential. In contrast, for knapsack problems using dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]), all values are initialized to zero since we're computing maximum values rather than counting combinations.

Implementation Examples

Knapsack Problem: Maximum Value with Capacity Constraint

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int itemCount, capacity;
    std::cin >> itemCount >> capacity;
    
    std::vector<int> weights(itemCount);
    std::vector<int> values(itemCount);
    
    for (int i = 0; i < itemCount; i++)
        std::cin >> weights[i];
    for (int i = 0; i < itemCount; i++)
        std::cin >> values[i];

    std::vector<std::vector<int>> dp(itemCount + 1, std::vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= itemCount; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (weights[i-1] > j)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = std::max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
        }
    }
    
    std::cout << dp[itemCount][capacity];
    return 0;
}

Combination Sum: Target Value Counting

class Solution {
public:
    int findTargetSumWays(std::vector<int>& nums, int target) {
        int totalSum = 0;
        for (int num : nums)
            totalSum += num;
        
        int subsetTarget = (totalSum + target) / 2;
        
        if ((totalSum + target) % 2 != 0 || std::abs(target) > totalSum)
            return 0;
            
        std::vector<std::vector<int>> dp(nums.size() + 1, std::vector<int>(subsetTarget + 1, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 0; j <= subsetTarget; j++) {
                dp[i][j] = dp[i-1][j];
                if (nums[i-1] <= j) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        
        return dp[nums.size()][subsetTarget];
    }
};