Noteathon / LC-DP

---

LC-DP

July 21, 2021

---

LC-Hashing

• LC-Hashing
• DP
  • Coin Change
  • Rob House
  • Paint Color houses
  • References
  • Next: Algorithms

---

DP

• Top Down vs Bottom Up ?
  • Top Down : Breaking large problems, into smaller problems and then solving the base cases.
  • Bottom Up : We start with the bases cases, where we use the solved problems and then solve the rest of the problems.

Coin Change

• Recursive solution :
  • Space : O(Amount/minDenomination) because if the amount is 10 and we have Coin of 2,3,5 then max we can do is minimal with 5*2 coins
  • Time : O(2^{Amount/minDenomination}).
• Why Power of 2, is because of the choice we have. Lets’s say we have 5 elements then we have 2⁵ choices.
• When done using TopDown,
  • Space : O(Amount * N)
  • Time : O(Amount * N) - since we are just fetching the value of the base cases which are presolved. Fetching will take O(1) which is done for all the sub problems - Amount * N.

Rob House

• Recursive approach :
  • Space : We are going to iterate each house or skip robbing then worst case Space : O(N)
  • Time : O(2^N), since here we have to two choices whether to rob the house or not.

Paint Color houses

• Recursive approach :
  • Space : : O(N); at any point houses are N only, not related with color.
  • Time : O(3 * 2^N-1) ~ (C-1)^n. where c color and n houses. Since first house we are checking all the cost to Paint House 1 with Red, then Blue and Green. So getting the minimum of all three. For the first house, we have 3 choices and the rest (n-1) houses we have two choices. ```java class Solution { int dp[][]; public static final int[] pColor0 = new int[]{1,2}; public static final int[] pColor1 = new int[]{0,2}; public static final int[] pColor2 = new int[]{0,1};

  public int minCost(int[][] costs) { dp = new int[101][4]; for(int[] row : dp){ Arrays.fill(row,-1); } int cost0 = paintHouse(costs, costs.length, 0); int cost1 = paintHouse(costs, costs.length, 1); int cost2 = paintHouse(costs, costs.length, 2);

    int maxVal = Math.min(cost0,Math.min(cost1,cost2));
    return maxVal;   }
  

  private int paintHouse(int[][] costs, int houseIdx, int paintColor){ if(houseIdx<=0){ return 0; }

    int paintCost = costs[houseIdx-1][paintColor];
      
    if(dp[houseIdx][paintColor]!=-1){
        return dp[houseIdx][paintColor];
    }
      
    if(paintColor == 0){
        int color1 = pColor0[0];
        int color2 = pColor0[1];
        return dp[houseIdx][paintColor] = paintCost + Math.min(paintHouse(costs, houseIdx-1, color1), 
                        paintHouse(costs, houseIdx-1, color2));
    }
      
    if(paintColor == 1){
        int color1 = pColor1[0];
        int color2 = pColor1[1];
        return dp[houseIdx][paintColor] = paintCost + Math.min(paintHouse(costs, houseIdx-1, color1), 
                        paintHouse(costs, houseIdx-1, color2));
    }
      
    if(paintColor == 2){
        int color1 = pColor2[0];
        int color2 = pColor2[1];
        return dp[houseIdx][paintColor] = paintCost + Math.min(paintHouse(costs, houseIdx-1, color1), 
                        paintHouse(costs, houseIdx-1, color2));
    }
      
    return 0;   } } ```
  

References

Next: Algorithms