1 D Dynamic Programming - ashishranjandev/interview-wiki GitHub Wiki

Dynamic programming is a powerful algorithmic technique used to solve problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once. It is particularly useful for optimization problems and problems with recursive structures. Dynamic programming stores the solutions to subproblems in a table to avoid redundant calculations and improve efficiency.

The key idea behind dynamic programming is the concept of memoization, which means storing the results of expensive function calls and reusing them when the same inputs occur again.

Here's a general approach to dynamic programming:

• Define the structure of the problem in terms of smaller subproblems.
• Determine the recurrence relation, which expresses the solution to a larger problem in terms of solutions to smaller subproblems.
• Create a memoization table (usually an array or a matrix) to store the solutions to subproblems as they are computed.
• Use a bottom-up or top-down approach to fill in the table and compute the solution to the original problem.

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
   
2. 2 steps
   

graph TD
      O[0]-->|1|01[1]
      O[0]-->|2|02[1]

      01[1]-->|1|011[2]
      01[1]-->|2|012[3]
      02[1]-->|1|021[3]
      02[1]-->|2|022[4]

      011[2]-->|1|0111[3]
      011[2]-->|2|0112[4]
      012[3]-->|1|0121[4]
      012[3]-->|2|0122[4]
      021[3]-->|1|0211[4]
      021[3]-->|2|0212[5]
      022[4]-->|1|0221[5]
      022[4]-->|2|0222[6]



      0111[3]-->|1|01111[4]
      0111[3]-->|2|01112[5]

      01111[4]-->|1|011111[5]
      01111[4]-->|1|011112[6]
      

classDef strikeThrough fill:#ffcccc,stroke:#f00,stroke-width:2px,text-decoration:line-through;
class 011112 strikeThrough;
class 0222 strikeThrough;

By Backtracking the time complexity would be O(2^n)

Here we can take a Memoization approach as we can see the sub-problems being calculated multiple times.
Hence we can create a cache for every subproblem and lookup before the backtracking call and add it to final sum.
By Memoization the time complexity would be O(n)

Here we start solving the problem from the last level of decision tree and work our way up.

If we start from position 5, number of ways to reach end is 1
If we start from position 4, number of ways to reach end is 1
If we start from position 3, number of ways to reach end is numbers(4) + numbers(5)
If we start from position 2, number of ways to reach end is numbers(3) + numbers(4)
If we start from position 1, number of ways to reach end is numbers(2) + numbers(3)

It looks like reverse fibonacci series.

public int climbStairs(int n) {
    int one = 1;
    int two = 2;
    int temp = 1;
    for (int i = 0; i < n - 1; i++) {
        temp = two;
        two = one + two;
        one = temp;
    }
    return one;
}

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top.
  The total cost is 15.
  

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
  
• Pay 1 and climb two steps to reach index 4.
  
• Pay 1 and climb two steps to reach index 6.
  
• Pay 1 and climb one step to reach index 7.
  
• Pay 1 and climb two steps to reach index 9.
  
• Pay 1 and climb one step to reach the top.
  

The total cost is 6.

graph TD
      O[0]-->|10|01[1]
      O[0]-->|10|02[2]


      01[1]-->|15|012[2]
      01[1]-->|15|013[3]

      02[2]-->|20|023[3]
      023 ~~~|"Total cost of this path<br/>30"| 023

      013 ~~~|"Total cost of this path<br/>25"| 013

      012[1]-->|20|0123[2]
      

      0123 ~~~|"Total cost of this path<br/>45"| 0123

We need to add an extra element to the array. We need to go from right to left and keep filling the cost.

cost[i] += Math.min(cost[i+1], cost[i+2]);

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

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

graph TD
      O[.]-->O1[1]
      O1[1]-->O13[3]
      O1[1]-->O11[1]

      O[.]-->O2[2]  
      O2[2]-->O21[1]  
      

      O13 ~~~|"Total loot of this path<br/>4"| O13
      O11 ~~~|"Total loot of this path<br/>4"| O11
      O21 ~~~|"Total loot of this path<br/>3"| O21

Array of houses and loots

Dividing the problem in subproblems

rob[0:n] = Max(arr[0] + rob[2:n], rob[1:n])

This is called recurrence relationship.

Creating the array which contains max, we can rob till this point. We can just modify the existing array to store these values.

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        # [rob1, rob2, n, n+1, ...]
        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        for (int i = 0; i < nums.length; i++) {
            int prev = (i >= 1) ? nums[i - 1] : 0;
            int prevsPrev = (i >= 2) ? nums[i - 2] : 0;
            nums[i] = Math.max(prevsPrev + nums[i], prev);
        }
        return nums[nums.length - 1];
    }
}

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount.
If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Can we try greedy solution?

We can have coins = [5,4,3,1] and target - 7
If we become greedy and try to solve using 5, we would end up with 3 coins i.e. 5,1,1

We can try DFS - Backtracking

We can have coins = [5,4,3,1] and target - 7
We can do bottom up as well.
We would calculate the number of coins, given we pick each coin.
Since for 1, n-3 would become negative, we ignore those values in min expression i.e. if the target is 4 there is no point picking coin 5.

DP[n] = Math.min(1 + DP[n - 1], 1 + DP[n - 3], 1 + DP[n - 4], 1 + DP[n -5])

public int coinChange(int[] coins, int amount) {
    int[] solutionArray = new int[amount + 1];
    solutionArray[0] = 0;
    int defaultValue = amount + 1;

    for (int targetIndex = 1; targetIndex < amount + 1; targetIndex++) {
        int minForTarget = defaultValue;
        for (int coinIndex = 0; coinIndex< coins.length; coinIndex++) {
            if (coins[coinIndex] <= targetIndex) {
                int coinUsingcoinAtCoinIndex = 1 + solutionArray[targetIndex - coins[coinIndex]];
                if (coinUsingcoinAtCoinIndex < minForTarget) {
                    minForTarget = coinUsingcoinAtCoinIndex;
                }
            }
        }
        solutionArray[targetIndex] = minForTarget;
    }
    return (solutionArray[amount] != defaultValue) ? solutionArray[amount] : -1;
}

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

We need to traverse over the array and keep track of max and min till now as the -ve value would flip the value.

Max till now = Math.max(curr * maxTillNow, curr * minTillNow, curr);
Min till now = Math.min(curr * maxTillNow, curr * minTillNow, curr);

If we encounter 0, We need to reset max and min to 1.

    public int maxProduct(int[] nums) {
        int answer = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > answer) {
                answer = num;
            }
        }
        int currentMax = 1;
        int currentMin = 1;

        for (int num : nums) {
            if (num == 0) {
                currentMax = 1;
                currentMin = 1;
            }
            int tempMax = currentMax;
            currentMax = Math.max(num * currentMax, Math.max(num * currentMin, num));
            currentMin = Math.min(num * tempMax, Math.min(num * currentMin, num));
            if (currentMax > answer) {
                answer = currentMax;
            }
        }
        return answer;
    }

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Instead of looking up in the input string in dictionary, we will lookup dictionary in the string.

graph TD
      O[i=0]-->O1["neet"]
      O[i=0]-->O2["leet"]
      O[i=0]-->O3["code"]

      O1["neet"]-->|i=4|O11["neet"]
      O1["neet"]-->|i=4|O12["leet"]
      O1["neet"]-->|i=4|O13["code"]

      O ~~~|"Dictionary<ul><li>neet</li><li>leet</li><li>code</li></ul>"| O
      O ~~~|"Input String<br/>neetcode"| O
      O13 ~~~|"This will return<br/>true"| O13

classDef strikeThrough fill:#ffcccc,stroke:#f00,stroke-width:2px,text-decoration:line-through;
class O2 strikeThrough;
class O3 strikeThrough;
class O11 strikeThrough;
class O12 strikeThrough;

We can do a bottom up approach

public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dpArray = new boolean[s.length() + 1];
    // Base Condition
    dpArray[s.length()] = true;

    // Starting the array from rear
    for (int i = s.length(); i >=0; i--) {
        for (String word : wordDict) {
            if (s.length() >= i + word.length() && s.substring(i, i + word.length()).equals(word)) {
                // If word is matching, check if the path reaches till end
                dpArray[i] = dpArray[i + word.length()];
                // If the path is there, just mark the current value as true and move to prev character
                if (dpArray[i]) {
                    break;
                }
            }
        }
    }
    return dpArray[0];
}

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example

Input: nums = [0,1,0,3,2,3]
Output: 4

Example

Input: nums = [7,7,7,7,7,7,7] Output: 1

where LIS(i) is Long increasing subsequence for array starting at index i.

public int lengthOfLIS(int[] nums) {
    int answer = 1;
    int[] lengthOfSubsequence = new int[nums.length];
    lengthOfSubsequence[nums.length - 1] = 1;
    for (int i = nums.length -2; i >=0; i--) {
        lengthOfSubsequence[i] = 1;
        for (int k = i + 1; k < nums.length; k++) {
            if (nums[i] < nums[k]) {
                lengthOfSubsequence[i] = Math.max(lengthOfSubsequence[i], 1 + lengthOfSubsequence[k]);
            }
        }
        answer = Math.max(lengthOfSubsequence[i], answer);
    }

    return answer;
}

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

For every element we have a choice to include them in decision tree or not.

We can a set of all possible sums of the array.
As we traverse we continue to add the new element to get all possible sums and all the new sums to the set.
At the end we just check if sum/2 is present in the set or not.

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }

    Set<Integer> possibleSums = new HashSet<>();
    possibleSums.add(0);

    for (int i = nums.length - 1; i >= 0; i--) {
        Set<Integer> setForItem = new HashSet<>();
        for (Integer possibleSum : possibleSums) {
            setForItem.add(possibleSum + nums[i]);
        }
        possibleSums.addAll(setForItem);
    }

    return possibleSums.contains(sum / 2);
}