easy-level-dp.cpp

// ⚡ 1. What is Dynamic Programming?
// 💡 Core Idea

// Dynamic Programming is used when:

// Overlapping Subproblems → same work repeated
// Optimal Substructure → answer depends on smaller answers

// 👉 Example:
// Fibonacci:

// fib(5) = fib(4) + fib(3)
// fib(4) = fib(3) + fib(2)

// 👉 fib(3) is repeated → waste

// 🧠 DP Approach Flow
// 1. Write Recursion
// 2. Add Memoization (Top-Down)
// 3. Convert to Tabulation (Bottom-Up)
// 4. Optimize Space (if possible)
// ⚡ 2. Recursion → Memoization → Tabulation ⭐⭐⭐
// 🔁 Step 1: Recursion

// Solve problem by breaking into smaller parts

// 🧠 Step 2: Memoization

// Store results in dp[]

// 📊 Step 3: Tabulation

// Build solution from base case

// 🪜 Thinking Steps
// Define state
// Write recurrence relation
// Identify base case
// Add DP storage
// Optimize
// ⚡ 3. Fibonacci ⭐
// 🔁 Recursion
// fib(n) = fib(n-1) + fib(n-2)
// 🧠 Memoization

// Store computed values

// 📊 Tabulation

// Build from bottom

// 🪜 Steps
// Define state → dp[i] = ith fibonacci

// Base:

// dp[0] = 0
// dp[1] = 1

// Transition:

// dp[i] = dp[i-1] + dp[i-2]
// ❓ Practice
// Find fib(n) for n = 50
// Print full DP array
// ⚡ 4. Climbing Stairs ⭐⭐
// 💡 Idea

// You can take:

// 1 step
// 2 steps

// 👉 Total ways = combinations

// 🔁 Recursion
// f(n) = f(n-1) + f(n-2)
// 🪜 Steps
// State → dp[i] = ways to reach step i

// Base:

// dp[0] = 1
// dp[1] = 1

// Transition:

// dp[i] = dp[i-1] + dp[i-2]
// ❓ Practice
// n = 5 → answer?
// Modify for 1,2,3 steps allowed
// ⚡ 5. Frog Jump (1-step / 2-step) ⭐⭐
// 💡 Idea

// Minimize energy

// cost[i] = min(
//     cost[i-1] + abs(h[i] - h[i-1]),
//     cost[i-2] + abs(h[i] - h[i-2])
// )
// 🪜 Steps
// State → min energy to reach i

// Base:

// dp[0] = 0
// Transition → take min of jumps
// ❓ Practice
// heights = [10,20,30,10]
// Solve manually
// ⚡ 6. House Robber I ⭐⭐⭐
// 💡 Idea

// Cannot rob adjacent houses

// 🔁 Recursion
// f(i) = max(
//     take = arr[i] + f(i-2),
//     not_take = f(i-1)
// )
// 🪜 Steps
// State → max money till i

// Base:

// dp[0] = arr[0]

// Transition:

// dp[i] = max(dp[i-1], arr[i] + dp[i-2])
// ❓ Practice
// [2,7,9,3,1]
// ⚡ 7. Minimum Cost Climbing Stairs ⭐⭐
// 💡 Idea

// Reach top with minimum cost

// 🪜 Steps
// State → min cost to reach i

// Base:

// dp[0] = cost[0]
// dp[1] = cost[1]

// Transition:

// dp[i] = cost[i] + min(dp[i-1], dp[i-2])
// ❓ Practice
// cost = [10,15,20]
// ⚡ 8. Grid Unique Paths ⭐⭐
// 💡 Idea

// Move:

// Right
// Down
// 🪜 Steps
// State → ways to reach (i,j)

// Base:

// dp[0][0] = 1

// Transition:

// dp[i][j] = dp[i-1][j] + dp[i][j-1]
// ❓ Practice
// 3×3 grid
// ⚡ 9. Grid Paths with Obstacles ⭐⭐
// 💡 Idea

// Same as above but avoid blocked cells

// 🪜 Steps
// If obstacle → dp = 0

// Else:

// dp[i][j] = top + left
// ❓ Practice
// Grid with 1 blocked cell
// ⚡ 10. Basic 2D DP (Matrix DP Intro)
// 💡 Idea

// State depends on neighbors

// Examples:

// Paths
// Minimum path sum
// 🪜 Pattern
// dp[i][j] depends on:
//     dp[i-1][j]
//     dp[i][j-1]
// ❓ Practice
// Minimum path sum
// ⚡ 11. Subset Sum ⭐⭐
// 💡 Idea

// Can we make sum?

// 🔁 Recursion
// f(i, sum) =
//     take OR not take
// 🪜 Steps
// State → dp[i][sum]

// Base:

// sum == 0 → true

// Transition:

// dp[i][s] = dp[i-1][s] OR dp[i-1][s-arr[i]]
// ❓ Practice
// arr = [2,3,7,8], sum = 11
// ⚡ 12. Coin Change (Count Ways) ⭐⭐
// 💡 Idea

// Unlimited coins

// 🔁 Recursion
// f(i, target) =
//     take + not_take
// 🪜 Steps
// State → dp[i][target]

// Base:

// target == 0 → 1 way

// Transition:

// dp[i][t] = dp[i][t - coin[i]] + dp[i-1][t]
// ❓ Practice
// coins = [1,2,5], target = 5
// 🚀 FINAL LEARNING STRATEGY

// For EVERY DP problem follow:

// 1. Try recursion first
// 2. Draw recursion tree
// 3. Identify overlapping
// 4. Add memoization
// 5. Convert to tabulation
// 6. Optimize space








// ⚡ 1. Fibonacci ⭐
// 💡 Mathematical Idea

// This follows a recurrence relation:

// F(n)=F(n−1)+F(n−2)

// 👉 Linear recurrence → forms a sequence

// 🧠 Algorithm Steps
// Define state: f(n)
// Base: f(0)=0, f(1)=1
// Use recurrence to build up



#include<bits/stdc++.h>
using namespace std;
//using recursion
int fib(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    return fib(n-1)+fib(n-2);
}
//using memoization
int fib_memo(int n,vector<int>&dp){
    if(n==0) return 0;
    if(n==1) return 1;
    if(dp[n]!=-1) return dp[n];
    return dp[n]=fib_memo(n-1,dp)+fib_memo(n-2,dp);
}
//using tabulation
int fib_tab(int n){
    vector<int>dp(n+1);
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}
int main(){
int n;
cin>>n;
cout<<"Fibonacci using recursion: "<<fib(n)<<endl;
vector<int>dp(n+1,-1);
cout<<"Fibonacci using memoization: "<<fib_memo(n,dp)<<endl;
cout<<"Fibonacci using tabulation: "<<fib_tab(n)<<endl;
return 0;
}




// ⚡ 2. Climbing Stairs ⭐⭐
// 💡 Idea

// Same as Fibonacci → combinations
// f(n)=f(n−1)+f(n−2)

// 🧠 Algorithm
// State: ways to reach step i
// Base: dp[0]=1, dp[1]=1
// Transition: dp[i]=dp[i−1]+dp[i−2]


#include<bits/stdc++.h>
using namespace std;
//using tabulation
int climbStairs(int n){
    vector<int>dp(n+1);
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}
int main(){
    int n;
    cin>>n;
    cout<<"Ways to climb"<<n<<"stairs: "<<climbStairs(n)<<endl;
    return 0;
}




// ⚡ 3. Frog Jump ⭐⭐
// 💡 Mathematical Idea
// Minimize cost: dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]),dp[i-2] + abs(h[i] - h[i-2])
// 👉 Similar to Fibonacci but with cost

// 🧠 Algorithm
// State: min energy to reach i
// Choose min of 1-step or 2-step jump
// Base: dp[0]=0
// Transition: dp[i]=min(dp[i-1]+cost1,dp[i-2]+cost2)






#include<bits/stdc++.h>
using namespace std;
int frogJump(int n,vector<int>& h){
    vector<int>dp(n);
    dp[0]=0;
    for(int i=1;i<n;i++){
        int cost1=dp[i-1]+abs(h[i]-h[i-1]);
        int cost2=INT_MAX;
        if(i>1){
            cost2=dp[i-2]+abs(h[i]-h[i-2]);
        }
        dp[i]=min(cost1,cost2);
    }
    return dp[n-1];
}
int main(){
    int n;
    cin>>n;
    vector<int>h(n);
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    cout<<"Minimum energy to reach end: "<<frogJump(n,h)<<endl;//output minimum energy to reach end if heights are given as input 2 3, 1,4 and n is 4=> output is 3
    return 0;
}






// ⚡ 4. House Robber ⭐⭐⭐
// 💡 Mathematical Idea
// dp[i]=max(dp[i−1], arr[i]+dp[i−2])

// 🧠 Algorithm
// State: max profit till i
// Decision:
// Take
// Not take
// Base: dp[0]=arr[0]
// Transition: dp[i]=max(dp[i-1],arr[i]+dp[i-2])
// ❓ Practice
// arr=[2,7,9,3,1] → answer?
// Output: 12 (rob 2,9,1)




#include<bits/stdc++.h>
using namespace std;
int houseRobber(vector<int>&arr){
    int n=arr.size();
    vector<int>dp(n);
    dp[0]=arr[0];
    for(int i=1;i<n;i++){
        int take=arr[i];
        if(i>1){
            take+=dp[i-2];
        }
        int not_take=dp[i-1];
        dp[i]=max(take,not_take);
    }
    return dp[n-1];
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Maximum amount that can be robbed: "<<houseRobber(arr)<<endl;//output maximum amount that can be robbed if arr is given as input 2,7,9,3,1 and n is 5=> output is 12
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
int minCost(vector<int>&cost){
    int n=cost.size();
    vector<int>dp(n);
    dp[0]=cost[0];
    dp[1]=cost[1];
    for(int i=2;i<n;i++){
        dp[i]=cost[i]+min(dp[i-1],dp[i-2]);
    }
    return min(dp[n-1],dp[n-2]);
}
int main(){
    int n;
    cin>>n;
    vector<int>cost(n);
    for(int i=0;i<n;i++){
        cin>>cost[i];
    }
    cout<<"Minimum cost to reach top: "<<minCost(cost)<<endl;//output minimum cost to reach top if cost is given as input 10,15,20 and n is 3=> output is 15
    return 0;
}



// ⚡ 6. Grid Unique Paths ⭐⭐
// 💡 Mathematical Idea
// dp[i][j]=dp[i−1][j]+dp[i][j−1]
// 👉 Paths in grid → move right or down
// 🧠 Algorithm
// State: ways to reach (i,j)
// Base: dp[0][0]=1
// Transition: dp[i][j]=dp[i-1][j]+dp[i][j-1]
// ❓ Practice
// 3×3 grid → answer?
// Input: m=3, n=3
// 
// Output: 6 (RRDD, RDRD, RDDR, DRRD, DRDR, DDRR)



#include<bits/stdc++.h>
using namespace std;
int GridUniquePaths(int m,int n){
    vector<vector<int>>dp(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i==0 && j==0){
                dp[i][j]=1;
            }
            else{
                int up=0,left=0;
                if(i>0){
                    up=dp[i-1][j];
                }
                if(j>0){
                    left=dp[i][j-1];
                }
                dp[i][j]=up+left;
            }
        }
    }
    return dp[m-1][n-1];
}
int main(){
    int m,n;
    cin>>m>>n;
    cout<<"Unique paths in "<<m<<"x"<<n<<" grid: "<<GridUniquePaths(m,n)<<endl;//output unique paths in mxn grid if m and n are given as input 3 and 3=> output is 6
    return 0;
}




// ⚡ 7. Grid Paths with Obstacles ⭐⭐
// 💡 Mathematical Idea
// If obstacle → dp=0
// Else → dp[i][j]=dp[i−1][j]+dp[i][j−1]
// 👉 Similar to unique paths but with blocked cells
// 🧠 Algorithm
// State: ways to reach (i,j)
// Base: dp[0][0]=1 if no obstacle
// Transition: if obstacle → dp=0 else dp[i][j]=dp[i-1][j]+dp[i][j-1]
// ❓ Practice
// Grid with 1 blocked cell → answer?
// Input: grid=[[0,0,0],[0,1,0],[0,0,0]]
// Output: 2 (RRDD, DDRR)





#include<bits/stdc++.h>
using namespace std;
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m=grid.size();
    int n=grid[0].size();
    vector<vector<int>>dp(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                dp[i][j]=0;
            }
            else if(i==0 && j==0){
                dp[i][j]=1;
            }
            else{
                int up=0,left=0;
                if(i>0){
                    up=dp[i-1][j];
                }
                if(j>0){
                    left=dp[i][j-1];
                }
                dp[i][j]=up+left;
            }
        }
    }
    return dp[m-1][n-1];
}
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>>grid(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>grid[i][j];
        }
    }
    cout<<"Unique paths with obstacles: "<<uniquePathsWithObstacles(grid)<<endl;
  return 0;
}




// ⚡ 8. Subset Sum ⭐⭐
// 💡 Mathematical Idea
// dp[i][s]=dp[i−1][s]∨dp[i−1][s−ai]
// 👉 Can we make sum s using first i elements
// 🧠 Algorithm
// State: can we achieve sum s using first i elements
// Base: dp[0][0]=1 (we can achieve sum 0 with 0 elements)
// Transition: dp[i][s]=dp[i−1][s]∨dp[i−1][s−ai]
// ❓ Practice
// arr=[2,3,7,8], sum=11 → answer?
// Input: arr=[2,3,7,8], sum=11
// Output: 1 (subset [3,8] sums to 11)





#include<bits/stdc++.h>
using namespace std;
bool subsetSum(vector<int>&arr,int sum){
    int n=arr.size();
     vector<vector<bool>>dp(n+1,vector<bool>(sum+1));
     for(int i=0;i<=n;i++){
            for(int s=0;s<=sum;s++){
                if(s==0){
                    dp[i][s]=true;
                }
                else if(i==0){
                    dp[i][s]=false;
                }
                else{
                    bool not_take=dp[i-1][s];
                    bool take=false;
                    if(s>=arr[i-1]){
                        take=dp[i-1][s-arr[i-1]];
                    }
                    dp[i][s]=not_take||take;
                }

            }
     }
    return dp[n][sum];
}
int main(){
    int n,sum;
    cin>>n>>sum;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    if(subsetSum(arr,sum)){
        cout<<"Subset with given sum exists."<<endl;
    }
    else{
        cout<<"Subset with given sum does not exist."<<endl;
    }
}



// ⚡ 9. Coin Change (Count Ways) ⭐⭐
// 💡 Mathematical Idea
// dp[i][t]=dp[i][t−coin(i)]+dp[i−1][t]
// 👉 Count ways to make change for target t using coins
// 🧠 Algorithm
// State: number of ways to make change for target t using first i coins
// Base: dp[0][0]=1 (one way to make sum 0 - use no coins)
// Transition: dp[i][t]=dp[i][t−coin(i)]+dp[i−1][t]
// ❓ Practice
// coins=[1,2,5], target=5 → answer?
// Input: coins=[1,2,5], target=5
// Output: 4 (ways: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5])



#include<bits/stdc++.h>
using namespace std;
int coinChange(vector<int>&coins,int target){
    int n=coins.size();
    vector<vector<int>>dp(n+1,vector<int>(target+1,0));
    for(int i=0;i<=n;i++){
        for(int t=0;t<=target;t++){
            if(t==0){
                dp[i][t]=1;
            }
            else if(i==0){
                dp[i][t]=0;
            }
            else{
                int not_take=dp[i-1][t];
                int take=0;
                if(t>=coins[i-1]){
                    take=dp[i][t-coins[i-1]];
                }
                dp[i][t]=take+not_take;
            }          
        }
    }
    return dp[n][target];
}
int main(){
    int n,target;
    cin>>n>>target;
    vector<int>coins(n);
    for(int i=0;i<n;i++){
        cin>>coins[i];
    }
    cout<<"Number of ways to make change: "<<coinChange(coins,target)<<endl;//output number of ways to make change if coins and target are given as input coins=[1,2,5] and target=5=> output is 4
    return 0;
}