Intro

Dynamic programming is a method used to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions.

To implement dynamic programming:

  • Identify Subproblems: Divide the main problem into smaller, independent subproblems.
  • Store Solutions: Solve each subproblem and store the solution.
  • Use Solutions: Use the stored solutions to build up the solution to the main problem.

There are two approaches to dynamic programming:

  1. Top-Down (Memoization): Start from the top (main problem) and break it down into subproblems. Store the results of subproblems in a data structure (e.g., hash map) to avoid redundant computations.
  2. Bottom-Up (Tabulation): Start from the bottom (subproblems) and build up the solution to the main problem. This approach is often more efficient in terms of space complexity.

Generally, you can solve a problem using either approach, but the choice depends on the problem and the constraints. During interviews, a good strategy is to first solve the problem using a simple recursive approach, then find a top-down dynamic programming solution. Ideally, the top-down approach will lead you to a bottom-up solution.

Example: Fibonacci Sequence

The Fibonacci sequence is a classic example of a problem that can be solved using dynamic programming. The sequence is defined as:

1, 1, 2, 3, 5, 8, 13, 21, ...

Each number in the sequence is the sum of the two preceding numbers. The naive recursive approach to calculating the nth Fibonacci number has exponential time complexity, as it recalculates the same subproblems multiple times.

/* Recursive approach */

int fib(int n) {
    if (n <= 1){
        return n;
    }
    return fib(n-1) + fib(n-2);
}

Diagram of the recursive calls for fib(5):

                             fib(5)
                 ┌──────────────┴──────────────┐
               fib(4)                        fib(3)
         ┌───────┴───────┐             ┌───────┴───────┐
       fib(3)          fib(2)        fib(2)          fib(1)
     ┌───┴────┐      ┌───┴───┐     ┌───┴───┐
   fib(2)  fib(1)  fib(1) fib(0) fib(1) fib(0)
 ┌───┴───┐
fib(1)  fib(0)

For an input of 5, the recursive function calls fib(3) twice, fib(2) three times, and fib(1) five times. To avoid this redundancy, we can use memoization (top-down DP) to store the results of subproblems.

/* Dynamic programming approach */

// Create a hash map to store the results of subproblems (memoization)
Map<Integer, Integer> memo = new HashMap<>(); 

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    // Check if the result is already stored in the memo. If it is,
    // don't recalculate, just return the stored result.
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    int result = fib(n-1) + fib(n-2); // calculate the subproblem
    memo.put(n, result); // store the solution
    return result;
}

New diagram of the call to fib(5):

                     fib(5)
                ┌──────┴──────┐
              fib(4)         fib(3)
          ┌─────┴─────┐            
        fib(3)       fib(2)
      ┌───┴────┐ 
    fib(2)   fib(1) 
  ┌───┴───┐
fib(1)  fib(0)

By storing the results of subproblems in the memo hash map, the function avoids redundant computations. The time complexity of this approach is linear, as each subproblem is solved only once.

Bottom-up dynamic programming can also be used to solve the Fibonacci sequence efficiently without recursion. This approach builds up the solution from the bottom by solving subproblems iteratively.

/* Bottom-up dynamic programming approach */

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    int[] dp = new int[n + 1]; // create an array to store the results
    dp[0] = 1; // base case
    dp[1] = 1; // base case
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // calculate the next Fibonacci number
    }
    return dp[n]; // return the nth Fibonacci number
}

Note: The Fibonacci sequence is a simple example to illustrate dynamic programming and the bottom-up solution may seem obvious. However, for more complex problems, figuring out the top-down approach first can help you understand the subproblems and build up to a bottom-up solution.

1) Climbing Stairs

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?

Example 1:

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

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

2) Longest Increasing Subsequence

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

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

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 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

3) Coin Change

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 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

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

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

4) Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100