Dynamic Programming

Dynamic Programming Algorithms in C++

A comprehensive guide to dynamic programming algorithms with code implementations and problem-solving patterns.

Table of Contents

1. Basic DP Problems
2. Pick/Not Pick Pattern
3. Infinite Pick Pattern
4. Grid/Path DP
5. String DP
6. Subsequence DP
7. Partition DP

---

Basic DP Problems

1. Fibonacci Series (Optimized)

Problem: Calculate nth Fibonacci number using DP optimization Pattern: Basic memoization and space optimization

#include<bits/stdc++.h>
using namespace std;

int fun(int n,unordered_map<int,int> &mp){
    if(n<=2) return 1;
    if(mp.find(n)!=mp.end()) return mp[n];
    return mp[n]=fun(n-1,mp)+fun(n-2,mp);
}
int fun2(int n,unordered_map<int,int> &mp){
    mp[0]=1;
    mp[1]=1;
    for(int i=2; i<n; i++){
        mp[i]=mp[i-1]+mp[i-2];
    }
    return mp[n-1];
}
int fun3(int n){
    int var1=1,var2=1;
    int temp;
    for(int i=2;i<n;i++){
        temp=var1+var2;
        var1=var2;
        var2=temp;
    }
    return temp;   
}
int main(){
    unordered_map<int,int> mp;
    cout<<fun3(10)<<endl;
}

Logic:

• Memoization: Store computed results to avoid recomputation
• Tabulation: Bottom-up approach using iterative method
• Space Optimization: Use only two variables instead of array
• Time Complexity: O(n), Space Complexity: O(1) for optimized version

---

Pick/Not Pick Pattern

2. 0/1 Knapsack Problem

Problem: Maximum value with weight constraint (each item used once) Pattern: Pick/Not Pick with weight constraint

#include <bits/stdc++.h> 
using namespace std;
int recusive(int n,int mw,vector<int> weight,vector<int> value,map<pair<int,int>,int> &dp){
	if(n==0){
		if(weight[0]<=mw) return value[0];
		return 0;
	}
	if(dp.find({n,mw})!=dp.end()) return dp[{n,mw}];
	int notpick=0+recusive(n-1,mw,weight,value,dp);
	int pick=0;
	if(weight[n]<=mw) pick=value[n]+recusive(n-1,mw-weight[n],weight,value,dp);
	return dp[{n,mw}]=max(pick,notpick);
}
int iterativeKnapsack(int n, int mw, vector<int> &weight, vector<int> &value, map<pair<int,int>,int> &dp) {
     for (int j = weight[0]; j <= mw; j++)
        dp[{0,j}] = value[0];

    // DP table filling
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= mw; j++) {
            int notpick = dp[{i - 1, j}];
            int pick = 0;
            if (weight[i - 1] <= j) // use i-1 for 0-indexed vectors
                pick = value[i - 1] + dp[{i - 1, j - weight[i - 1]}];
            dp[{i, j}] = max(notpick, pick);
        }
    }

    return dp[{n, mw}];
}

Logic:

• State: dp[i][w] = maximum value using first i items with weight limit w
• Transition: max(not_pick, pick_if_weight_allows)
• Base Case: Single item fits or doesn't fit
• Time Complexity: O(nW), Space Complexity: O(nW)

3. Subset Sum Problem

Problem: Check if subset with given sum exists Pattern: Pick/Not Pick with sum constraint

#include <bits/stdc++.h> 
using namespace std; 
map<pair<int,int>,bool> dp;
bool subsetSumToK(int n, int k, vector<int> &arr) {
    if(k==0) return true;
    if(n==0) return arr[0]==k;
    if(dp.find({n,k})!=dp.end()) return dp[{n,k}];
    bool notpick=subsetSumToK( n-1,k,arr);
    bool pick=false;
    if(arr[n]<=k){
        pick=subsetSumToK( n-1,k-arr[n],arr);
    }
    return dp[{n,k}]=pick|notpick;
}
bool subsetSumToKloop(int n, int k, vector<int> &arr) {
    dp[{0,0}]=true;
    for(int i=1;i<=n;i++){
        dp[{i,0}]=true;
        for(int j=0;j<=k;j++){
            bool take=dp[{i-1,j}];
            bool nottake=false;
            if(arr[i]<=j) nottake=dp[{i-1,j-arr[i]}];
            dp[{i,j}]=take|nottake;
        }
    }
    return dp[{n,k}];
}

Logic:

• State: dp[i][sum] = true if sum is possible using first i elements
• Transition: pick current element or don't pick
• Base Case: sum=0 is always possible, single element cases
• Time Complexity: O(nsum), Space Complexity: O(nsum)

4. House Robber (Non-Adjacent Elements)

Problem: Maximum sum without picking adjacent elements Pattern: Pick/Not Pick with adjacency constraint

#include<bits/stdc++.h>
using namespace std;

class Solution {
    unordered_map<int,int> mp;
public:
    int picknotpick(int n,vector<int>& nums){
        if(n==0) return nums[0];
        if(n<0) return 0;
        if(mp.find(n)!=mp.end()) return mp[n];
        int pick=nums[n]+picknotpick(n-2,nums);
        int notpick=0+picknotpick(n-1,nums);
        return mp[n]=max(pick,notpick);
    }
    int rob(vector<int>& nums) {
        return picknotpick(nums.size()-1,nums);
    }
};

Logic:

• State: dp[i] = maximum sum up to index i
• Transition: max(pick_current + dp[i-2], skip_current + dp[i-1])
• Constraint: Cannot pick adjacent elements
• Time Complexity: O(n), Space Complexity: O(n)

5. Partition Equal Subset Sum

Problem: Check if array can be partitioned into two equal sum subsets Pattern: Pick/Not Pick with target sum = total_sum/2

#include<bits/stdc++.h>
using namespace std;
bool subsetk(int n,int k,vector<int> &arr,map<pair<int,int>,bool> &dp){
	if(k==0) return 0;
	if(n==0) return arr[0]==k;
	if(dp.find({n,k})!=dp.end()) return dp[{n,k}];
	bool notpick=subsetk(n-1,k,arr,dp);
	bool pick=false;
	if(arr[n]<=k) pick=subsetk(n-1,k-arr[n],arr,dp);
	return dp[{n,k}]=pick|notpick;
}
bool canPartition(vector<int> &arr, int n)
{
	map<pair<int,int>,bool> dp;
	int total =accumulate(arr.begin(),arr.end(),0);
	if(total%2==0) return subsetk(arr.size()-1,total/2,arr,dp);
	return false;
}

Logic:

• Insight: If total sum is odd, partition impossible
• Target: Find subset with sum = total_sum/2
• Optimization: Only need to check one subset (other will have remaining sum)
• Time Complexity: O(nsum), Space Complexity: O(nsum)

---

Infinite Pick Pattern

6. Coin Change (Minimum Coins)

Problem: Minimum coins needed to make target amount Pattern: Infinite pick with minimization

#include<bits/stdc++.h>
using namespace std;

class Solution {
    public:
        int recusive(int n,int target,vector<int>& coins,map<pair<int,int>,int> &dp){
            if(target==0) return 0;
            if(n==0){
                if(coins[0]==target) return 1;
                else if(target%coins[0]==0) return target/coins[0];
                else return INT_MAX-1;
            }
            if(dp.find({n,target})!=dp.end()) return dp[{n,target}];
            int notpick=0+recusive(n-1,target,coins,dp);
            int pick=INT_MAX-1;
            if(target>=coins[n]) pick=1+recusive(n,target-coins[n],coins,dp);
           
            return dp[{n,target}]=min(notpick,pick);;
        }
        int coinChange(vector<int>& coins, int amount) {
            map<pair<int,int>,int> dp;
            int temp=recusive(coins.size()-1,amount,coins,dp);
            if(temp==INT_MAX-1) return -1;
            return temp;
        }
    };

Logic:

• State: dp[i][amount] = minimum coins using first i coin types
• Transition: min(not_use_coin, use_coin + dp[i][amount-coin_value])
• Key: Same coin can be used multiple times (infinite supply)
• Time Complexity: O(namount), Space Complexity: O(namount)

7. Coin Change II (Count Ways)

Problem: Number of ways to make target amount Pattern: Infinite pick with counting

#include<bits/stdc++.h>
using namespace std;
class Solution {
    public:
        int recursive(int n,int target,vector<int>& coins,map<pair<int,int>,int> &dp){
            if(target==0) return 1;
            if(n==0){
                if(target%coins[0]==0) return 1;
                else return 0;
            }
            if(dp.find({n,target})!=dp.end()) return dp[{n,target}];
            int notpick=recursive(n-1,target,coins,dp);
            int pick=0;
            if(target>=coins[n]) pick=recursive(n,target-coins[n],coins,dp);
            return dp[{n,target}]=notpick+pick;
        }
        int change(int amount, vector<int>& coins) {
            map<pair<int,int>,int> dp;
            return recursive(coins.size()-1,amount,coins,dp);
        }
    };

Logic:

• State: dp[i][amount] = number of ways using first i coin types
• Transition: ways_without_coin + ways_with_coin
• Base Case: amount=0 has 1 way (use no coins)
• Time Complexity: O(namount), Space Complexity: O(namount)

---

Grid/Path DP

8. Frog Jump (Minimum Cost)

Problem: Minimum cost to reach end with 1 or 2 step jumps Pattern: Path DP with cost optimization

#include <bits/stdc++.h> 
using namespace std;
int f(int n, vector<int> &heights,unordered_map<int,int> &mp){
    if(n==0) return 0;
    if(mp.find(n)!=mp.end()) return mp[n];
    int left=f(n-1,heights,mp)+abs(heights[n]-heights[n-1]);
    int right=INT_MAX;
    if(n>1) right=f(n-2,heights,mp)+abs(heights[n]-heights[n-2]);
    return mp[n]=min(left,right);
}
int f3(int n,vector<int> &heights){
    int prev1=0,prev2=0,curr=0;
    for(int i=1;i<=n;i++){
        int ff=prev1+abs(heights[i]-heights[i-1]);
        int ss=INT_MAX;
        if(i>1) ss=prev2+abs(heights[i]-heights[i-2]);
        curr=min(ss,ff);
        prev2=prev1;
        prev1=curr;
    }
    return curr;
}

Logic:

• State: dp[i] = minimum cost to reach position i
• Transition: min(cost_from_i-1, cost_from_i-2) + current_cost
• Space Optimization: Only need previous 2 values
• Time Complexity: O(n), Space Complexity: O(1) optimized

9. Frog Jump K Steps

Problem: Minimum cost with up to K step jumps Pattern: Path DP with variable steps

#include <bits/stdc++.h>
using namespace std;

class Solution {
    unordered_map<int,int> mp;
  public:
    int recurcive(int n,int k,vector<int>& arr){
        if(n==0) return 0;
        if(mp.find(n)!=mp.end()) return mp[n];
        int minsteep=INT_MAX;
        for(int i=1;i<=k;i++){
            if(n-i>=0){
                int jump=recurcive(n-i,k,arr)+abs(arr[n]-arr[n-i]);
                minsteep=min(minsteep,jump);
            }
        }
        return mp[n]=minsteep;
    }
    int minimizeCost(int k, vector<int>& arr) {
        mp[0]=0;
       return recurcive(arr.size()-1,k,arr);
    }
};

Logic:

• State: dp[i] = minimum cost to reach position i
• Transition: Try all possible jumps from 1 to k steps
• Optimization: Check all valid previous positions
• Time Complexity: O(n*k), Space Complexity: O(n)

10. Ninja Training (Grid DP with Constraints)

Problem: Maximum points with constraint (no same activity on consecutive days) Pattern: Grid DP with choice constraints

#include<bits/stdc++.h>
using namespace std;

map<pair<int,int>,int> mp;
int bc(int index,int prev,vector<vector<int>> &arr){
    if(index==0){
        int maxi=0;
        for(int i=0;i<3;i++){
            if(i!=prev){
                maxi=max(maxi,arr[index][i]);
            }
        }
        return maxi;
    }
    if(mp.find({index,prev})!=mp.end()) return mp[{index,prev}];
    int maxi=0;
    for(int i=0;i<3;i++){
        if(i!=prev){
            maxi=max(maxi,arr[index][i]+bc(index-1,i,arr));
        }
    }
    return mp[{index,prev}]=maxi;
}

Logic:

• State: dp[day][last_activity] = maximum points up to day with last activity
• Constraint: Cannot do same activity on consecutive days
• Transition: Try all activities except the previous one
• Time Complexity: O(n3), Space Complexity: O(n3)

---

String DP

11. Longest Common Subsequence (LCS)

Problem: Find length of longest common subsequence between two strings Pattern: String matching DP

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<pair<int,dir>>> arr(text1.size()+1,vector<pair<int,dir>>(text2.size()+1,{0,NONE}));
        for(int i=0;i<text1.size();i++){
            for(int j=0;j<text2.size();j++){
                if(text1[i]==text2[j]){
                    arr[i+1][j+1].first=1+arr[i][j].first;
                    arr[i+1][j+1].second=DIA;
                }
                else if(arr[i][j+1].first>arr[i+1][j].first){
                    arr[i+1][j+1].first=arr[i][j+1].first;
                    arr[i+1][j+1].second=UP;
                } else {
                    arr[i+1][j+1].first=arr[i+1][j].first;
                    arr[i+1][j+1].second=RIGHT;
                }
            }
        }
        return arr[text1.size()][text2.size()].first;
    }
};

Logic:

• State: dp[i][j] = LCS length for first i chars of str1 and first j chars of str2
• Transition: If chars match: 1 + dp[i-1][j-1], else: max(dp[i-1][j], dp[i][j-1])
• Applications: Edit distance, diff algorithms, DNA sequence analysis
• Time Complexity: O(mn), Space Complexity: O(mn)

---

Subsequence DP

12. Longest Increasing Subsequence (LIS)

Problem: Find length of longest increasing subsequence Pattern: Subsequence DP with ordering constraint

#include<bits/stdc++.h>
using namespace std;
int longestIncreasingSubsequence(int arr[], int n)
{
    vector<int> dp(n,1);
    int mux=0;
    for(int i=1;i<n;i++){
        mux=0;
        for(int j=0;j<i;j++){
            if(arr[j]<arr[i]) mux=max(mux,dp[j]);
        }
        dp[i]=max(dp[i],1+mux);
    }
    for(int it:dp) mux=max(mux,it);
    return mux;
}

Logic:

• State: dp[i] = length of LIS ending at index i
• Transition: For each previous element < current, extend its LIS
• Optimization: Binary search approach exists for O(n log n)
• Time Complexity: O(n²), Space Complexity: O(n)

---

Partition DP

13. Count Partitions with Given Difference

Problem: Count ways to partition array into two subsets with given difference Pattern: Partition DP with constraint transformation

#include<bits/stdc++.h>
using namespace std;

int countsubset(int n,int k,vector<int> &arr,map<pair<int,int>,int> &dp){
    if (n == 0) {
        if(k==0&&arr[0]==0) return 2;
        if(k==0&&k==arr[0]) return 1;
        return 0;
    }
    if(dp.find({n,k})!=dp.end()) return dp[{n,k}];
    int notpick=countsubset(n-1,k,arr,dp);
    int pick=0;
    if(arr[n]<=k) pick=countsubset(n-1,k-arr[n],arr,dp);
    return dp[{n,k}]=pick+notpick;
}
int findWays(vector<int>& arr, int k)
{
    map<pair<int,int>,int> dp;
	return countsubsettable(arr.size()-1,k,arr,dp);
}

Logic:

• Transformation: If S1 - S2 = D and S1 + S2 = Total, then S1 = (Total + D)/2
• Problem Reduction: Count subsets with sum = (Total + D)/2
• Edge Cases: Handle zeros and impossible cases
• Time Complexity: O(nsum), Space Complexity: O(nsum)

---

Key DP Patterns Summary

1. Memoization vs Tabulation

• Memoization: Top-down recursive approach with caching
• Tabulation: Bottom-up iterative approach
• Space Optimization: Reduce space by keeping only necessary previous states

2. State Design Principles

• Identify Variables: What changes in each subproblem?
• State Representation: How to uniquely represent each subproblem?
• Transition: How to compute current state from previous states?

3. Common DP Patterns

Pick/Not Pick Template:

int dp(int index, int constraint) {
    if (base_case) return base_value;
    if (memo[index][constraint] != -1) return memo[index][constraint];
    
    int not_pick = dp(index + 1, constraint);
    int pick = 0;
    if (can_pick) pick = value + dp(index + 1, new_constraint);
    
    return memo[index][constraint] = max(pick, not_pick);
}

Grid DP Template:

int dp(int i, int j) {
    if (i == 0 && j == 0) return grid[0][0];
    if (i < 0 || j < 0) return infinity;
    if (memo[i][j] != -1) return memo[i][j];
    
    int up = dp(i-1, j);
    int left = dp(i, j-1);
    
    return memo[i][j] = grid[i][j] + min(up, left);
}

String DP Template:

int dp(int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    
    if (str1[i-1] == str2[j-1]) {
        return memo[i][j] = 1 + dp(i-1, j-1);
    } else {
        return memo[i][j] = max(dp(i-1, j), dp(i, j-1));
    }
}

4. Optimization Techniques

• Space Optimization: Use rolling arrays when only previous row/column needed
• State Compression: Reduce dimensions when possible
• Early Termination: Stop computation when answer found
• Preprocessing: Precompute frequently used values

5. Problem Recognition

• Optimal Substructure: Can problem be broken into smaller subproblems?
• Overlapping Subproblems: Are same subproblems solved multiple times?
• Decision Making: Are there choices to make at each step?
• Constraints: What limitations affect the choices?

This comprehensive guide covers all major dynamic programming patterns with working code examples and detailed explanations of the logic behind each approach.