Dynamic Programming

‣

Pattern 1 : Minimum (Maximum) Path to Reach a Target

Problem Identification

Given a target goal is to achieve target with minimum (maximum) cost / path / sum.

Here basically we have targets and some ways to achieve it with value of maximum/minimum cost/path/sum.

Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.


routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

Generate optimal solutions for all values in the target and return the value for the target.

Problem 1: ‣

Identify Pattern :

Target : To reach top of stairs and each stair has cost

Ways : we can either take 1 step or 2 step

Solution :

Recursive top-down : we try to solve smaller problem (i-1) and based on the answer of last step(i-1), we build answer for the current step (i) and to fetch the all possible answer from i-1 step, we call i-1 with all possible ways.

Memoization : There is multiple repeated same recursive function call subtree, instead of calculating the answer for those small problem again, we memorize them to return last the same if requried later.

DP bottom up: As we can see how recursion is getting solved - it has answer for the smaller problem i-1 and i-2 step then it answer for the ith step, so basically we need to know state of last 2 sub-problem to answer i th problem (moving iteratively).


class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // int n = cost.length;
        // int memo[] = new int[n+1];
        // Arrays.fill(memo,Integer.MAX_VALUE);
        // int c1 = minCostClimbingStairsHelper(cost,0,memo);
        // int c2 = minCostClimbingStairsHelper(cost,1,memo);

        // return Math.min(c1,c2);


        int n = cost.length;
        int c1=0, c2 = 0;
        for(int i=n-1;i>=0;i--){
            if(i+1==n){
                c1  = cost[i];
                c2 = 0;
            } else{
                int c = Math.min(c1,c2)+cost[i];
                c2 = c1;
                c1 = c;
            }
        }

        return Math.min(c1,c2);

    }

    int minCostClimbingStairsHelper(int []cost, int step, int []memo){
        int n = cost.length;

        if(step==n) {
           return 0;
        }
        
        if(memo[step]!=Integer.MAX_VALUE) return memo[step];
        
        int c1 = cost[step], c2 = cost[step];
        if(step+1<=n) c1 += minCostClimbingStairsHelper(cost, step+1,memo);
        if(step+2<=n) c2 += minCostClimbingStairsHelper(cost, step+2,memo);
        memo[step] = Math.min(c1,c2);
        
        return memo[step];
    }
}

Problem 2: ‣

Identify Pattern :

Target: Here target is reach the end of matrix at minimum path sum.

Ways: we can either move down, right.

Solution

Recursive - Top Down : Moving through each cell with all possible ways till we reach the end of cell, basically to answer cost to reach cell[n-1,m-1] from cell [0,0] we first fetch answer from all possible ways [1,0], [0,1] and then choosing minimum of them and adding cost of current cell

int result = min(pathSum(i+1, j, grid, memo), pathSum(i, j+1, grid, memo)) + grid[i][j];

Memoization : Memoize the result for the cell which already traversed , and return memoized answer when traversing them again


class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int memo[][] = new int[n][m];
        for(int arr[]:memo){
            Arrays.fill(arr,-1);
        }
        return minPathSumHelper(grid,0,0, memo);
    }

    int minPathSumHelper(int [][]grid, int i , int j, int memo[][]){
        int n = grid.length;
        int m = grid[0].length;

        if(i==n-1 && j==m-1) return grid[i][j];
        if(memo[i][j]!=-1) return memo[i][j];     
       

      memo[i][j] = Math.min(i+1<n ? minPathSumHelper(grid,i+1,j,memo):Integer.MAX_VALUE,
                            j+1<m ? minPathSumHelper(grid,i,j+1,memo): Integer.MAX_VALUE) 
                            + grid[i][j];
        return memo[i][j];
    }
}

DP - Bottom Up: What is smallest problem in recursive approach ?

when there is matrix with one cell. right ?

if matrix is having one row then sum[0][j] = matrix[0][j]+sum[0][j+1]; here j+1 < n

matrix[][] = [[3,4,5,6]]
sum[][] = [18,15,11,6] so minimum cost is 18.

Now assume there is 2 row okay, if we have know answer for last row’s each element to reach end of matrix then easily we can answer what the cost to each row 1 to row 2

Simply dp[i][j] = Math.min( dp[i+1][j], dp[i][j+1]) + matix[i][j]; - as there is only two direction to move.

2nd Approach : Loop

Problem 3: ‣

Identify Pattern :

Target: We have to achieve given amount. eg: 11

Ways : Give array of coins. eg: coins = [1,2,5],

Recursive : We can start with taking all possible ways and smaller will be solved recursively and we can increment count by 1 for our action on smaller problem count returned by recursion


for (int i = 0; i < coins.size(); ++i) {
	if (coins[i] <= target) { // check validity of a sub-problem
		result = min(ans, CoinChange(target - coins[i], coins) + 1);
	}
}
return result;

Memoization: As there is many same repeated recursive sub-problems occurs we can memoize their result with avoid solving same repeated problem.

DP Bottom Up :

Simple approach iterate the target range with solving each iterative element in all possible ways

means double nested loop - iterate target and inner loop all possible ways and build the answer from the alredy filled dp from the previous iterations.


for (int j = 1; j <= amount; ++j) {
   for (int i = 0; i < coins.size(); ++i) {
       if (coins[i] <= j) {
           dp[j] = min(dp[j], dp[j - coins[i]] + 1);
       }
   }
}