Common DP Patterns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

def multi_dimensional_knapsack_2d(
    n: int,
    values: list[int],
    weights: list[int],
    volumes: list[int],
    max_weight: int,
    max_volume: int
) -> int:
    """
    2-dimensional 0/1 knapsack: maximize value subject to weight AND volume constraints.
    
    Args:
        n: Number of items
        values: values[i] = value of item i
        weights: weights[i] = weight of item i
        volumes: volumes[i] = volume of item i
        max_weight: Maximum weight capacity
        max_volume: Maximum volume capacity
    
    Returns:
        Maximum achievable value
    
    Time Complexity: O(n × W × V)
    Space Complexity: O(W × V)
    """
    # dp[w][v] = max value with at most w weight and v volume
    dp = [[0] * (max_volume + 1) for _ in range(max_weight + 1)]
    
    for i in range(n):
        val = values[i]
        wt = weights[i]
        vol = volumes[i]
        
        # Iterate backwards to avoid using same item twice
        for w in range(max_weight, wt - 1, -1):
            for v in range(max_volume, vol - 1, -1):
                dp[w][v] = max(dp[w][v], dp[w - wt][v - vol] + val)
    
    return dp[max_weight][max_volume]
 
 
def multi_dimensional_knapsack_kd(
    n: int,
    values: list[int],
    requirements: list[list[int]],  # requirements[i][j] = item i's consumption of resource j
    capacities: list[int]  # capacities[j] = max capacity of resource j
) -> int:
    """
    k-dimensional 0/1 knapsack for arbitrary number of constraints.
    
    Uses a flattened representation for arbitrary dimensions.
    
    Time Complexity: O(n × product of capacities)
    Space Complexity: O(product of capacities)
    """
    k = len(capacities)
    
    # Flatten multi-dimensional DP into 1D using index calculation
    def flatten_index(indices: list[int]) -> int:
        idx = 0
        multiplier = 1
        for d in range(k - 1, -1, -1):
            idx += indices[d] * multiplier
            multiplier *= (capacities[d] + 1)
        return idx
    
    total_states = 1
    for c in capacities:
        total_states *= (c + 1)
    
    dp = [0] * total_states
    
    # Helper to iterate through all states in reverse order
    def iterate_states_reverse():
        """Generate all valid states in reverse order (for 0/1 knapsack)."""
        indices = list(capacities)  # Start at max
        while True:
            yield list(indices)
            
            # Decrement with carry
            for d in range(k):
                if indices[d] > 0:
                    indices[d] -= 1
                    break
                else:
                    indices[d] = capacities[d]
            else:
                break  # All dimensions wrapped around
    
    for i in range(n):
        val = values[i]
        reqs = requirements[i]
        
        # Process states in reverse order within feasible region
        for state in iterate_states_reverse():
            # Check if this state can accommodate item i
            if all(state[d] >= reqs[d] for d in range(k)):
                prev_state = [state[d] - reqs[d] for d in range(k)]
                
                curr_idx = flatten_index(state)
                prev_idx = flatten_index(prev_state)
                
                dp[curr_idx] = max(dp[curr_idx], dp[prev_idx] + val)
    
    return dp[flatten_index(capacities)]
 
 
def knapsack_2d_with_items(
    n: int,
    values: list[int],
    weights: list[int],
    volumes: list[int],
    max_weight: int,
    max_volume: int
) -> tuple[int, list[int]]:
    """
    2D knapsack with item reconstruction.
    """
    # Need full DP table for reconstruction
    dp = [[[0, []] for _ in range(max_volume + 1)] for _ in range(max_weight + 1)]
    
    for i in range(n):
        val = values[i]
        wt = weights[i]
        vol = volumes[i]
        
        for w in range(max_weight, wt - 1, -1):
            for v in range(max_volume, vol - 1, -1):
                prev_val, prev_items = dp[w - wt][v - vol]
                new_val = prev_val + val
                
                if new_val > dp[w][v][0]:
                    dp[w][v] = [new_val, prev_items + [i]]
    
    return dp[max_weight][max_volume][0], dp[max_weight][max_volume][1]
 
 
# Example
if __name__ == "__main__":
    # Project selection: budget limit $100, time limit 50 hours
    # Project i: value[i], cost[i], time[i]
    
    values = [60, 100, 120, 80, 90]  # Returns
    weights = [20, 30, 40, 25, 35]   # Costs (budget consumption)
    volumes = [10, 20, 25, 15, 20]   # Time (hours)
    max_weight = 100  # Budget
    max_volume = 50   # Time
    
    n = len(values)
    
    max_value = multi_dimensional_knapsack_2d(n, values, weights, volumes, 
                                               max_weight, max_volume)
    print(f"Maximum value: {max_value}")
    
    max_value, selected = knapsack_2d_with_items(n, values, weights, volumes,
                                                  max_weight, max_volume)
    print(f"Maximum value: {max_value}")
    print(f"Selected items: {selected}")
    print(f"Total cost: {sum(weights[i] for i in selected)}")
    print(f"Total time: {sum(volumes[i] for i in selected)}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

def count_subsets_with_sum_and_size(
    nums: list[int], 
    k: int, 
    target: int
) -> int:
    """
    Count subsets with exactly k elements that sum to target.
    
    Args:
        nums: Array of integers (can include duplicates)
        k: Required subset size
        target: Required sum
    
    Returns:
        Number of such subsets
    
    Time Complexity: O(n × k × target)
    Space Complexity: O(k × target)
    """
    n = len(nums)
    
    # dp[j][s] = ways to choose j elements summing to s
    # from elements processed so far
    dp = [[0] * (target + 1) for _ in range(k + 1)]
    dp[0][0] = 1  # One way to choose 0 elements with sum 0
    
    for num in nums:
        # Process in reverse to avoid using same element twice
        for j in range(min(k, n), 0, -1):  # Number of elements
            for s in range(target, num - 1, -1):  # Sum
                dp[j][s] += dp[j - 1][s - num]
    
    return dp[k][target]
 
 
def count_ways_to_form_target(
    nums: list[list[int]], 
    target: int
) -> int:
    """
    LeetCode 1079/1155 style: Given groups of numbers, count ways to select
    exactly one from each group such that selected numbers sum to target.
    
    Args:
        nums: nums[i] = list of available values in group i
        target: Required sum
    
    Returns:
        Number of ways modulo 10^9 + 7
    """
    MOD = 10**9 + 7
    
    # dp[s] = ways to achieve sum s with groups processed so far
    dp = [0] * (target + 1)
    dp[0] = 1
    
    for group in nums:
        new_dp = [0] * (target + 1)
        
        for prev_sum in range(target + 1):
            if dp[prev_sum] == 0:
                continue
            
            for val in group:
                new_sum = prev_sum + val
                if new_sum <= target:
                    new_dp[new_sum] = (new_dp[new_sum] + dp[prev_sum]) % MOD
        
        dp = new_dp
    
    return dp[target]
 
 
def partition_equal_subset_sum_count(nums: list[int]) -> int:
    """
    Count ways to partition array into two subsets with equal sum.
    
    If total sum is odd, return 0.
    Otherwise, count subsets summing to total/2.
    Each partition corresponds to exactly 2 subsets (the selected and complement),
    so divide final count by 2 if counting unordered partitions.
    """
    total = sum(nums)
    
    if total % 2 != 0:
        return 0
    
    target = total // 2
    n = len(nums)
    
    # dp[s] = number of subsets summing to s
    dp = [0] * (target + 1)
    dp[0] = 1
    
    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    
    # Each partition is counted once (subset A, complement is subset B)
    # If we want unordered partitions, divide by 2
    # But typically we return dp[target] as is
    return dp[target]
 
 
def count_subsets_with_bounded_sum(
    nums: list[int], 
    low: int, 
    high: int
) -> int:
    """
    Count subsets with sum in range [low, high].
    
    Approach: count subsets with sum ≤ high, subtract those with sum < low.
    """
    def count_up_to(target: int) -> int:
        if target < 0:
            return 0
        
        # dp[s] = number of subsets with sum exactly s
        dp = [0] * (target + 1)
        dp[0] = 1
        
        for num in nums:
            if num > target:
                continue
            for s in range(target, num - 1, -1):
                dp[s] += dp[s - num]
        
        return sum(dp)  # All subsets with sum ≤ target
    
    return count_up_to(high) - count_up_to(low - 1)
 
 
# Example
if __name__ == "__main__":
    # Count subsets of size 3 that sum to 10
    nums = [1, 2, 3, 4, 5, 6]
    k = 3
    target = 10
    
    count = count_subsets_with_sum_and_size(nums, k, target)
    print(f"Subsets of size {k} summing to {target}: {count}")
    # Subsets: {1,3,6}, {1,4,5}, {2,3,5} = 3
    
    # Ways to select from groups
    groups = [[1, 2], [2, 3], [3, 4]]
    target_sum = 7
    ways = count_ways_to_form_target(groups, target_sum)
    print(f"Ways to select one per group summing to {target_sum}: {ways}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

def count_subsets_divisible_by_k(nums: list[int], k: int) -> int:
    """
    Count non-empty subsets whose sum is divisible by k.
    
    Key insight: We only need to track sum mod k, not the actual sum.
    
    Time Complexity: O(n × k)
    Space Complexity: O(k)
    """
    # dp[r] = number of subsets with sum ≡ r (mod k)
    dp = [0] * k
    dp[0] = 1  # Empty subset has sum 0
    
    for num in nums:
        new_dp = dp.copy()  # Include subsets not using this number
        
        for r in range(k):
            # Add num to subsets with remainder r
            new_r = (r + num) % k
            new_dp[new_r] += dp[r]
        
        dp = new_dp
    
    # Subtract 1 for empty subset if we want non-empty only
    return dp[0] - 1
 
 
def max_sum_divisible_by_k(nums: list[int], k: int) -> int:
    """
    Find maximum sum of a subset that is divisible by k.
    
    LeetCode 1262: dp[r] = max sum among subsets with sum ≡ r (mod k)
    """
    INF = float('inf')
    
    # dp[r] = max sum with remainder r, or -INF if not achievable
    dp = [-INF] * k
    dp[0] = 0  # Empty subset: sum 0
    
    for num in nums:
        new_dp = dp.copy()
        
        for r in range(k):
            if dp[r] == -INF:
                continue
            
            new_r = (r + num) % k
            new_dp[new_r] = max(new_dp[new_r], dp[r] + num)
        
        dp = new_dp
    
    return dp[0] if dp[0] > 0 else 0
 
 
def count_numbers_divisible_by_m_up_to_n(n: int, m: int) -> int:
    """
    Count positive integers from 1 to n that are divisible by m.
    
    Simple math: floor(n / m)
    
    But for more complex conditions, use digit DP.
    """
    return n // m
 
 
def digit_dp_count_divisible(n: str, m: int) -> int:
    """
    Digit DP: Count numbers from 0 to n (as string) divisible by m.
    
    State: (position, remainder, tight, started)
    - position: current digit position
    - remainder: current number mod m
    - tight: whether we're still bounded by n
    - started: whether we've placed a non-zero digit (for leading zeros)
    """
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(pos: int, rem: int, tight: bool, started: bool) -> int:
        if pos == len(n):
            # End of number: count if divisible and number actually formed
            return 1 if (rem == 0 and started) else 0
        
        limit = int(n[pos]) if tight else 9
        result = 0
        
        for digit in range(0, limit + 1):
            new_tight = tight and (digit == limit)
            new_started = started or (digit > 0)
            
            if new_started:
                new_rem = (rem * 10 + digit) % m
            else:
                new_rem = 0  # Leading zeros don't affect remainder
            
            result += dp(pos + 1, new_rem, new_tight, new_started)
        
        return result
    
    return dp(0, 0, True, False)
 
 
def count_special_numbers(n: int, m: int, d: int) -> int:
    """
    Count numbers from 1 to n that:
    1. Are divisible by m
    2. Contain digit d at least once
    
    Uses inclusion-exclusion with digit DP.
    """
    from functools import lru_cache
    
    n_str = str(n)
    
    @lru_cache(maxsize=None)
    def dp(pos: int, rem: int, tight: bool, has_d: bool, started: bool) -> int:
        if pos == len(n_str):
            return 1 if (rem == 0 and has_d and started) else 0
        
        limit = int(n_str[pos]) if tight else 9
        result = 0
        
        for digit in range(0, limit + 1):
            new_tight = tight and (digit == limit)
            new_started = started or (digit > 0)
            new_has_d = has_d or (digit == d)
            
            if new_started:
                new_rem = (rem * 10 + digit) % m
            else:
                new_rem = 0
            
            result += dp(pos + 1, new_rem, new_tight, new_has_d, new_started)
        
        return result
    
    return dp(0, 0, True, False, False)
 
 
# Examples
if __name__ == "__main__":
    nums = [3, 1, 7, 5]
    k = 5
    
    count = count_subsets_divisible_by_k(nums, k)
    print(f"Non-empty subsets with sum divisible by {k}: {count}")
    
    max_sum = max_sum_divisible_by_k(nums, k)
    print(f"Maximum sum divisible by {k}: {max_sum}")
    
    # Digit DP example
    n = "100"
    m = 7
    count = digit_dp_count_divisible(n, m)
    print(f"Numbers 1-{n} divisible by {m}: {count}")
    # Should be 14 (7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

def knapsack_2d_space_optimized(
    n: int,
    values: list[int],
    weights: list[int],
    volumes: list[int],
    max_weight: int,
    max_volume: int
) -> int:
    """
    2D knapsack with O(max_volume) space instead of O(max_weight × max_volume).
    
    Key insight: If we process weight in outer loop (backward),
    we only need the current 'row' of the volume dimension.
    """
    # For 0/1 knapsack, we can process both backwards and use 1D...
    # Actually, for 2D 0/1 knapsack, we still need the 2D table
    # because we need dp[w-wt][v-vol] and that might be from same w-layer.
    
    # But we can reduce to O(V) if we iterate cleverly:
    # Process each item, and for each item, update in place.
    
    # Full space version is actually necessary for 2D 0/1 knapsack
    # unless using more complex tricks.
    
    # Here's the standard implementation:
    dp = [[0] * (max_volume + 1) for _ in range(max_weight + 1)]
    
    for i in range(n):
        val, wt, vol = values[i], weights[i], volumes[i]
        for w in range(max_weight, wt - 1, -1):
            for v in range(max_volume, vol - 1, -1):
                dp[w][v] = max(dp[w][v], dp[w - wt][v - vol] + val)
    
    return dp[max_weight][max_volume]
 
 
def sparse_knapsack_2d(
    items: list[tuple[int, int, int]],  # (value, weight, volume)
    max_weight: int,
    max_volume: int
) -> int:
    """
    Sparse 2D knapsack using dictionary for states.
    Better when many states are unreachable.
    """
    # states: dict of (weight, volume) -> max_value
    states = {(0, 0): 0}
    
    for value, weight, volume in items:
        new_states = {}
        
        for (w, v), val in states.items():
            # Option 1: Don't take this item
            key = (w, v)
            if key not in new_states or new_states[key] < val:
                new_states[key] = val
            
            # Option 2: Take this item (if feasible)
            new_w, new_v = w + weight, v + volume
            if new_w <= max_weight and new_v <= max_volume:
                new_val = val + value
                key = (new_w, new_v)
                if key not in new_states or new_states[key] < new_val:
                    new_states[key] = new_val
        
        states = new_states
    
    return max(states.values())
 
 
def meet_in_middle_subset_sum_2d(
    items: list[tuple[int, int, int]],  # (value, cost1, cost2)
    cap1: int,
    cap2: int
) -> int:
    """
    Meet in the middle for 2D knapsack-like problem.
    
    Split items into two halves, enumerate all subsets of each,
    then find best combination where total costs don't exceed caps.
    
    Time: O(2^(n/2) × n/2) + O(2^(n/2) × log(2^(n/2))) for sorting/searching
    """
    n = len(items)
    mid = n // 2
    
    first_half = items[:mid]
    second_half = items[mid:]
    
    def generate_all_subsets(item_list):
        """Generate all (value, cost1, cost2) combinations for subsets."""
        result = [(0, 0, 0)]  # Empty subset
        
        for value, c1, c2 in item_list:
            new_result = []
            for v, cc1, cc2 in result:
                new_result.append((v, cc1, cc2))  # Without this item
                new_result.append((v + value, cc1 + c1, cc2 + c2))  # With this item
            result = new_result
        
        return result
    
    first_subsets = generate_all_subsets(first_half)
    second_subsets = generate_all_subsets(second_half)
    
    # Filter second half by feasibility and organize for efficient lookup
    # For each cost1 value in second half, track (max value achievable for cost2 ≤ x)
    
    from collections import defaultdict
    
    # Simple approach: sort second half, for each first half entry, binary search
    second_subsets = [(v, c1, c2) for v, c1, c2 in second_subsets 
                      if c1 <= cap1 and c2 <= cap2]
    
    # For efficiency, preprocess: for each c1, track best values by c2
    best_for_c1 = defaultdict(list)
    for v, c1, c2 in second_subsets:
        best_for_c1[c1].append((c2, v))
    
    # Sort and compute prefix max for each c1
    from bisect import bisect_right
    
    prefix_max = {}
    for c1, entries in best_for_c1.items():
        entries.sort()  # by c2
        # Compute prefix max of value
        max_vals = []
        running_max = 0
        for c2, v in entries:
            running_max = max(running_max, v)
            max_vals.append(running_max)
        prefix_max[c1] = (entries, max_vals)
    
    best = 0
    
    for v1, c1_first, c2_first in first_subsets:
        if c1_first > cap1 or c2_first > cap2:
            continue
        
        remaining_c1 = cap1 - c1_first
        remaining_c2 = cap2 - c2_first
        
        # Find best second-half subset with c1 ≤ remaining_c1 and c2 ≤ remaining_c2
        for c1_second in range(remaining_c1 + 1):
            if c1_second not in prefix_max:
                continue
            
            entries, max_vals = prefix_max[c1_second]
            
            # Binary search for c2 ≤ remaining_c2
            c2_list = [e[0] for e in entries]
            idx = bisect_right(c2_list, remaining_c2) - 1
            
            if idx >= 0:
                best_v2 = max_vals[idx]
                best = max(best, v1 + best_v2)
    
    return best
 
 
# Example
if __name__ == "__main__":
    items = [(60, 20, 10), (100, 30, 20), (120, 40, 25)]
    max_w, max_v = 50, 40
    
    standard = knapsack_2d_space_optimized(
        len(items),
        [x[0] for x in items],
        [x[1] for x in items],
        [x[2] for x in items],
        max_w, max_v
    )
    print(f"Standard 2D knapsack: {standard}")
    
    sparse = sparse_knapsack_2d(items, max_w, max_v)
    print(f"Sparse 2D knapsack: {sparse}")