Dynamic Programming

Here are some classic Dynamic Programming interview questions.

We recommend: Climbing Stairs, Best Time to Buy and Sell Stock and Maximum Subarray.

70. Climbing Stairs

leetcode.com/problems/climbing-stairs/solution/

3번으로 풀었다. 4번부터 쬐끔 당황쓰.

Summary

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

Approach 1: Brute Force

Algorithm

In this brute force approach we take all possible step combinations i.e. 1 and 2, at every step. At every step we are calling the function climbStairs for step 1 and 2, and return the sum of returned values of both functions.

climbStairs(i,n)=(i + 1, n) + climbStairs(i + 2, n)

where i defines the current step and n defines the destination step.

Complexity Analysis

Time complexity : O(2^n). Size of recursion tree will be 2^n.

Recursion tree for n=5 would be like this:
Space complexity : O(n). The depth of the recursion tree can go upto n.

Approach 2: Recursion with Memoization

Algorithm

In the previous approach we are redundantly calculating the result for every step. Instead, we can store the result at each step in memo array and directly returning the result from the memo array whenever that function is called again.

In this way we are pruning recursion tree with the help of memo array and reducing the size of recursion tree upto n.

Complexity Analysis

Time complexity : O(n). Size of recursion tree can go upto n.
Space complexity : O(n). The depth of recursion tree can go upto n.

Approach 3: Dynamic Programming

Algorithm

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem.

One can reach i^{th} step in one of the two ways:

Taking a single step from (i-1)^{th} step.
Taking a step of 2 from (i-2)^{th} step.

So, the total number of ways to reach i^{th} is equal to sum of ways of reaching (i-1)^{th} step and ways of reaching (i-2)^{th} step.

Let dp[i] denotes the number of ways to reach on i^{th} step:

dp[i]=dp[i-1]+dp[i-2]

Example:

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

Complexity Analysis

Time complexity : O(n). Single loop upto n.
Space complexity : O(n). dp array of size n is used.

Approach 4: Fibonacci Number

Algorithm

In the above approach we have used dp array where dp[i]=dp[i-1]+dp[i-2]. It can be easily analysed that dp[i] is nothing but i^{th} fibonacci number.

Fib(n)=Fib(n-1)+Fib(n-2)

Now we just have to find n^{th} number of the fibonacci series having 1 and 2 their first and second term respectively, i.e. Fib(1)=1 and Fib(2)=2.

Complexity Analysis

Time complexity : O(n). Single loop upto n is required to calculate n^{th} fibonacci number.
Space complexity : O(1). Constant space is used.

Approach 5: Binets Method

Algorithm

This is an interesting solution which uses matrix multiplication to obtain the n^{th} Fibonacci Number. The matrix takes the following form:

\left[ {\begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} } \right] = \left[ {\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} } \right]

Let's say Q=\left[ {\begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} } \right]. As per the method, the n^{th} Fibonacci Number is given by Q^{n-1}[0,0].

Let's look at the proof of this method.

We can prove this method using Mathematical Induction. We know, this matrix gives the correct result for the 3^{rd} term(base case). Since Q^2 = \left[ {\begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} } \right]. This proves that the base case holds.

Assume that this method holds for finding the n^{th} Fibonacci Number, i.e. F_n=Q^{n-1}[0,0], where Q^{n-1}=\left[ {\begin{array}{cc} F_{n} & F_{n-1} \\ F_{n-1} & F_{n-2} \end{array} } \right]

Now, we need to prove that with the above two conditions holding true, the method is valid for finding the (n+1)^{th} Fibonacci Number, i.e. F_{n+1}=Q^{n}[0,0].

Proof: Q^{n} = \left[ {\begin{array}{cc} F_{n} & F_{n-1} \\ F_{n-1} & F_{n-2} \end{array} } \right]\left[ {\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} } \right]. Q^{n} = \left[ {\begin{array}{cc} F_{n}+F_{n-1} & F_n \\ F_{n-1}+F_{n-2} & F_{n-1} \end{array} } \right] Q^{n} = \left[ {\begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} } \right]

Thus, F_{n+1}=Q^{n}[0,0]. This completes the proof of this method.

The only variation we need to do for our problem is that we need to modify the initial terms to 2 and 1 instead of 1 and 0 in the Fibonacci series. Or, another way is to use the same initial Q matrix and use result = Q^{n}[0,0] to get the final result. This happens because the initial terms we have to use are the 2nd and 3rd terms of the otherwise normal Fibonacci Series.

Complexity Analysis

Time complexity : O(\log n). Traversing on \log n bits.
Space complexity : O(1). Constant space is used.

Proof of Time Complexity:

Let's say there is a matrix M to be raised to power n. Suppose, n is the power of 2. Thus, n = 2^i, i\in\mathbb{N}, where \mathbb{N} represents the set of natural numbers(including 0). We can represent in the form of a tree:

Meaning that: M^n = M^{n/2}.M^{n/2} = .... = \prod_{1}^{n} M^{1}

So, to calculate M^{n} matrix, we should calculate M^{n/2} matrix and multiply it by itself. To calculate M^{n/2} we would have to do the same with M^{n/4} and so on.

Obviously, the tree height is \log_{2} n.

Let’s estimate M^{n} calculation time. M matrix is of the same size in any power . Therefore, we can perform the multiplication of two matrices in any power in O(1). We should perform \log_2 n of such multiplications. So, M^{n} calculation complexity is O(\log_{2} n).

In case, the number n is not a power of two, we can break it in terms of powers of 2 using its binary representation:

n= \sum_{p\in P} 2^{p}, \text{where }P\subset\mathbb{N}

Thus, we can obtain the final result using:

M^{n} = \prod_{p\in P} M^{2^{p}}

This is the method we've used in our implementation. Again, the complexity remains O(\log_{2} n) as we have limited the number of multiplications to O(\log_{2} n).

Approach 6: Fibonacci Formula

Algorithm

We can find n^{th} fibonacci number using this formula:

F_n = 1/\sqrt{5}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]

For the given problem, the Fibonacci sequence is defined by F_0 = 1, F_1= 1, F_1= 2, F_{n+2}= F_{n+1} + F_n. A standard method of trying to solve such recursion formulas is assume F_n of the form F_n= a^n. Then, of course, F_{n+1} = a^{n+1} and F_{n+2}= a^{n+2} so the equation becomes a^{n+2}= a^{n+1}+ a^n. If we divide the entire equation by an we arrive at a^2= a + 1 or the quadratic equation a^2 - a- 1= 0.

Solving this by the quadratic formula, we get:

a=1/\sqrt{5}\left(\left(\frac{1\pm \sqrt{5}}{2}\right)\right)

The general solution, thus takes the form:

F_n = A\left(\frac{1+\sqrt{5}}{2}\right)^{n} + B\left(\frac{1-\sqrt{5}}{2}\right)^{n}

For n=0, we get A + B = 1

For n=1, we get A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right) = 1

Solving the above equations, we get:

A = \left(\frac{1+\sqrt{5}}{2\sqrt{5}}\right), B = \left(\frac{1-\sqrt{5}}{2\sqrt{5}}\right)

Putting these values of A and B in the above general solution equation, we get:

F_n = 1/\sqrt{5}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right)

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

Complexity Analysis

Time complexity : O(\log n). pow method takes \log n time.
Space complexity : O(1). Constant space is used.

121. Best Time to Buy and Sell Stock

leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

Solution

We need to find out the maximum difference (which will be the maximum profit) between two numbers in the given array. Also, the second number (selling price) must be larger than the first one (buying price).

In formal terms, we need to find \max(\text{prices[j]} - \text{prices[i]}), for every i and j such that j > i.

Approach 1: Brute Force

Complexity Analysis

Time complexity : O(n^2). Loop runs \dfrac{n (n-1)}{2} times.
Space complexity : O(1). Only two variables - \text{maxprofit} and \text{profit} are used.

Approach 2: One Pass

Algorithm

Say the given array is:

[7, 1, 5, 3, 6, 4]

If we plot the numbers of the given array on a graph, we get:

The points of interest are the peaks and valleys in the given graph. We need to find the largest peak following the smallest valley. We can maintain two variables - minprice and maxprofit corresponding to the smallest valley and maximum profit (maximum difference between selling price and minprice) obtained so far respectively.

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1) return 0;
        
        int min = prices[0];
        int maxProfit = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] < min)
                min = prices[i];
            else if(prices[i] - min > maxProfit)
                maxProfit = prices[i] - min;
        }
        
        return maxProfit;
    }
}

Complexity Analysis

Time complexity : O(n). Only a single pass is needed.
Space complexity : O(1). Only two variables are used.

53. Maximum Subarray

leetcode.com/problems/maximum-subarray/

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

2번으로 풀었다. 3번 풀이가 정말 좋다고 생각한다. 그러나 내가 이걸 인터뷰에서 생각해낼수 있을까...

Solution

Approach 1: Divide and Conquer

Intuition

The problem is a classical example of divide and conquer approach, and can be solved with the algorithm similar with the merge sort.

Let's follow here a solution template for the divide and conquer problems :

Define the base case(s).
Split the problem into subproblems and solve them recursively.
Merge the solutions for the subproblems to obtain the solution for the original problem.

Algorithm

maxSubArray for array with n numbers:

If n == 1 : return this single element.
left_sum = maxSubArray for the left subarray, i.e. for the first n/2 numbers (middle element at index (left + right) / 2 always belongs to the left subarray).
right_sum = maxSubArray for the right subarray, i.e. for the last n/2 numbers.
cross_sum = maximum sum of the subarray containing elements from both left and right subarrays and hence crossing the middle element at index (left + right) / 2.
Merge the subproblems solutions, i.e. return max(left_sum, right_sum, cross_sum).

Implementation

class Solution {
  public int crossSum(int[] nums, int left, int right, int p) {
    if (left == right) return nums[left];

    int leftSubsum = Integer.MIN_VALUE;
    int currSum = 0;
    for(int i = p; i > left - 1; --i) {
      currSum += nums[i];
      leftSubsum = Math.max(leftSubsum, currSum);
    }

    int rightSubsum = Integer.MIN_VALUE;
    currSum = 0;
    for(int i = p + 1; i < right + 1; ++i) {
      currSum += nums[i];
      rightSubsum = Math.max(rightSubsum, currSum);
    }

    return leftSubsum + rightSubsum;
  }

  public int helper(int[] nums, int left, int right) {
    if (left == right) return nums[left];

    int p = (left + right) / 2;

    int leftSum = helper(nums, left, p);
    int rightSum = helper(nums, p + 1, right);
    int crossSum = crossSum(nums, left, right, p);

    return Math.max(Math.max(leftSum, rightSum), crossSum);
  }

  public int maxSubArray(int[] nums) {
    return helper(nums, 0, nums.length - 1);
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(N \log N). Let's compute the solution with the help of master theorem T(N) = aT\left(\frac{b}{N}\right) + \Theta(N^d). The equation represents dividing the problem up into a subproblems of size \frac{N}{b} in \Theta(N^d) time. Here one divides the problem in two subproblemes a = 2, the size of each subproblem (to compute left and right subtree) is a half of initial problem b = 2, and all this happens in a \mathcal{O}(N) time d = 1. That means that \log_b(a) = d and hence we're dealing with case 2 that means \mathcal{O}(N^{\log_b(a)} \log N) = \mathcal{O}(N \log N) time complexity.
Space complexity : \mathcal{O}(\log N) to keep the recursion stack.

Approach 2: Greedy

Intuition

The problem to find maximum (or minimum) element (or sum) with a single array as the input is a good candidate to be solved by the greedy approach in linear time. One can find the examples of linear time greedy solutions in our articles of
Super Washing Machines, and Gas Problem.

Pick the locally optimal move at each step, and that will lead to the globally optimal solution.

The algorithm is general and straightforward: iterate over the array and update at each step the standard set for such problems:

current element
current local maximum sum (at this given point)
global maximum sum seen so far.

Implementation

class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length;
    int currSum = nums[0], maxSum = nums[0];

    for(int i = 1; i < n; ++i) {
      currSum = Math.max(nums[i], currSum + nums[i]);
      maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(N) since it's one pass along the array.
Space complexity : \mathcal{O}(1), since it's a constant space solution.

Approach 3: Dynamic Programming (Kadane's algorithm)

Intuition

The problem to find sum or maximum or minimum in an entire array or in a fixed-size sliding window could be solved by the dynamic programming (DP) approach in linear time.

There are two standard DP approaches suitable for arrays:

Constant space one. Move along the array and modify the array itself.
Linear space one. First move in the direction left->right, then in the direction right->left. Combine the results. Here is an example.

Let's use here the first approach since one could modify the array to track the current local maximum sum at this given point.

Next step is to update the global maximum sum, knowing the local one.

Implementation

class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length, maxSum = nums[0];
    for(int i = 1; i < n; ++i) {
      if (nums[i - 1] > 0) nums[i] += nums[i - 1];
      maxSum = Math.max(nums[i], maxSum);
    }
    return maxSum;
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(N) since it's one pass along the array.
Space complexity : \mathcal{O}(1), since it's a constant space solution.

198. House Robber

leetcode.com/problems/house-robber/

마치 계단문제처럼 DP의 정석같은 문제인데, 과연 인터뷰에서 침착하고 재빠르게 설계할 수 있을지...

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1] Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 400

Solution

Approach #1 (Dynamic Programming) [Accepted]

Algorithm

It could be overwhelming thinking of all possibilities on which houses to rob.

A natural way to approach this problem is to work on the simplest case first.

Let us denote that:

f(k) = Largest amount that you can rob from the first k houses.
Ai = Amount of money at the ith house.

Let us look at the case n = 1, clearly f(1) = A1.

Now, let us look at n = 2, which f(2) = max(A1, A2).

For n = 3, you have basically the following two options:

Rob the third house, and add its amount to the first house's amount.
Do not rob the third house, and stick with the maximum amount of the first two houses.

Clearly, you would want to choose the larger of the two options at each step.

Therefore, we could summarize the formula as following:

f(k) = max(f(k – 2) + Ak, f(k – 1))

We choose the base case as f(–1) = f(0) = 0, which will greatly simplify our code as you can see.

The answer will be calculated as f(n). We could use an array to store and calculate the result, but since at each step you only need the previous two maximum values, two variables are suffice.

public int rob(int[] num) {
    int prevMax = 0;
    int currMax = 0;
    for (int x : num) {
        int temp = currMax;
        currMax = Math.max(prevMax + x, currMax);
        prevMax = temp;
    }
    return currMax;
}