Session 40: DP 2

Original Session

Date: 09 Feb 2025

Topic: DP

Concept: Way of solving problem.

Programs

1. Perfect Sum Problem
   1. GFG here

      public int perfectSum(int[] nums, int target) {
              
              int n = nums.length;
              int w = target;
              int mod = 1000000009;
              
              int[][] dp = new int[n+1][w+1];
              for (int i = 0; i<=n; i++) {
                  dp[i][0] = 1;
              }
              
              for (int i=1; i<=n; i++) {
                  
                  for (int j=0; j<=w; j++) {
                      
                      if (nums[i - 1] <= j) {
                          
                          dp[i][j] = (dp[i-1][j] + dp[i-1][j - nums[i-1]]) % mod;
                      } else {
                          
                          dp[i][j] = (dp[i-1][j]) % mod;
                      }
                  }
              }
              
              return dp[n][w];
          }

2. 416. Partition Equal Subset Sum
   1. leetcode here

      public boolean canPartition(int[] nums) {
              
              int sum = 0;
              for (int n: nums) {
                  sum += n;
              }
      
              if (sum % 2 != 0) {
      
                  return false;
              } else {
      
                  int target = sum/2;
                  int n = nums.length;
                  boolean[][] dp = new boolean[n+1][target+1];
                  for (int i=0; i<=n; i++) {
                      dp[i][0] = true;
                  } 
      
                  for (int i=1; i<=n; i++) {
      
                      for (int j=0; j<=target; j++) {
      
                          if (nums[i - 1] <= j) {
                          
                              dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
                          } else {
                              
                              dp[i][j] = dp[i-1][j];
                          }
                      }
                  }
      
                  return dp[n][target];
              }
          }

3. 494. Target Sum
   1. leetcode here

      public int findTargetSumWays(int[] nums, int target) {
              
              int n = nums.length;
              int sum = 0;
              for (int it: nums) {
                  sum += it;
              }
      
              if ((sum + target) % 2 != 0) {
                  return 0;
              }
              if (Math.abs(target) > sum) {
                  return 0;
              }
      
              int M = (sum + target) / 2;
              int[][] dp = new int[n+1][M+1];
              for (int i=0; i<=n; i++) {
                  dp[i][0] = 1;
              }
      
              for (int i=1; i<=n; i++) {
      
                  for (int j=0; j<=M; j++) {
      
                      if (nums[i-1] <= j) {
                          dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
                      } else {
                          dp[i][j] = dp[i-1][j];
                      }
                  }
              }
      
              return dp[n][M];
          }

4. Knapsack with Duplicate Items
   1. GFG here

      int knapSack(int val[], int wt[], int capacity) {
              
              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][j - wt[i-1]]);
                      } else {
                          dp[i][j] = dp[i-1][j];
                      }
                  }
              }
              
              return dp[n][w];
          }

5. 322. Coin Change
   1. leetcode here

      public int coinChange(int[] coins, int amount) {
              
              int m = coins.length;
              int n = amount;
              int[][] dp = new int[m+1][n+1];
      
              for (int j=1; j<=n; j++) {
                  dp[0][j] = Integer.MAX_VALUE-1;
              }
      
              for (int i=1; i<=m; i++) {
      
                  for (int j=1; j<=n; j++) {
      
                      if (j < coins[i-1]) {
      
                          dp[i][j] = dp[i-1][j];
                      } else {
      
                          dp[i][j] = Math.min(dp[i-1][j], 1+dp[i][j - coins[i-1]]);
                      }
                  }
              }
      
              return (dp[m][n] == Integer.MAX_VALUE - 1) ? -1 : dp[m][n];
          }