Session 39: DP 1

Original Session

Date: 08 Feb 2025

Topic: DP

Concept: Way of solving problem.
Overlapping Sub Problems.
Storing Solution and reusing it. - Memoization

Concept: Max Sum such that no two elements are are adjuscent (side by side).

int max = Math.max(memo[i-1], memo[i-2] + arr[i]);
memo[i] = memo[i-2] + arr[i]

Concept: 0/1 Knapsack here

Programs

1. 509. Fibonacci Number
   1. leetcode here

      public int fib(int n) {
              
            if (n <= 1) {
                return n;
            }
            int[] dp = new int[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];
      }

2. 70. Climbing Stairs
   1. leetcode here

      public int climbStairs(int n) {
              
          if (n <= 1) {
              return n;
          }
          int[] dp = new int[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];
      }

3. 1137. N-th Tribonacci Number
   1. leetcode here

          public int tribonacci(int n) {
              
              if (n <= 1) {
              return n;
              }
              int[] dp = new int[n+1];
              dp[0] = 0;
              dp[1] = 1;
              dp[2] = 1;
      
              for (int i=3; i<=n; i++) {
                  dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
              }
              return dp[n];
          }

4. 198. House Robber
   1. leetcode here

      public int rob(int[] nums) {
              
              if (nums.length == 1) {
                  return nums[0];
              }
      
              if (nums.length == 2) {
                  return Math.max(nums[0], nums[1]);
              }
      
              int[] memo = new int[nums.length];
              int max = 0;
              memo[0] = nums[0];
              memo[1] = Math.max(nums[0], nums[1]);
              for (int i=2; i<nums.length; i++) {
      
                  
                  memo[i] = Math.max(memo[i-1], memo[i-2] + nums[i]);
              }
              return memo[nums.length-1];
          }

5. 213. House Robber II
   1. leetcode here

      public int rob(int[] nums) {
              
              int n = nums.length;
              if (n == 0) {
                  return 0;
              }
      
              if (n == 1) {
                  return nums[0];
              }
      
              int[] ans1 = new int[n+1];
              int[] ans2 = new int[n+1];
              ans1[0] = nums[0];
              ans1[1] = Math.max(nums[0], nums[1]);
      
              for (int i=2; i<n-1; i++) {
                  ans1[i] = Math.max(ans1[i-1], ans1[i-2] + nums[i]);
              }
      
              ans2[0] = 0;
              ans2[1] = nums[1];
              for (int i=2; i<n; i++) {
                  ans2[i] = Math.max(ans2[i-1], ans2[i-2] + nums[i]);
              }
      
              return Math.max(ans1[n-2], ans2[n-1]);
          }

6. 746. Min Cost Climbing Stairs
   1. leetcode here

      public int minCostClimbingStairs(int[] cost) {
          
          int n = cost.length;
          int[] dp = new int[n];
      
          for (int i=0; i<n; i++) {
      
              if (i<2) {
                  dp[i] = cost[i];
              } else {
                  dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
              }
          }
      
          return Math.min(dp[n-1], dp[n-2]);
      }

7. 0/1 Knapsack Problem
   1. GFG here

      int knapSack(int capacity, int val[], int wt[]) {
              // code here
              
              int n = val.length;
              int w = capacity;
              int[][] dp = new int[n+1][w+1];
              
              for (int i=1; i<=n; i++) {
                  
                  for (int j=1; j<=w; j++) {
                      
                      if (wt[i-1] <= j) {
                          
                          dp[i][j] = Math.max(dp[i-1][j],
                                      val[i-1] + dp[i-1][j - wt[i-1]]);
                      } else {
                          dp[i][j] = dp[i-1][j];
                      }
                  }
              }
              
              return dp[n][w];
          }