2/3 some classic DP problems

Fibonacci

  • 递归 ✔️
  • 递归 + 记忆化搜索 ✔️
  • 动规 ✔️
  • Space Optimized 动规 ✔️
public class Solution {

    public int fibonacci(int n) {
        // base case
        if (n == 2) return 1;
        if (n == 1) return 0;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

_Time Complexity: _T(n) = T(n-1) + T(n-2) which is exponential. So this is a bad implementation for nth Fibonacci number. _Extra Space: _O(n) if we consider the function call stack size, otherwise O(1).

当输入n很大时，程序的效率会变得非常低，因此需要引入记忆化搜索 using HashMap.

public class Solution {

    Map<Integer, Integer> map = new HashMap<>();
    public int fibonacci(int n) {
        // write your code here
        if (n == 2 || n == 1) return n - 1;

        if (map.containsKey(n)) return map.get(n);

        int rst = fibonacci(n - 1) + fibonacci(n - 2);

        map.put(n, rst);
        return rst;
    }
}

引入记忆化搜索后，大大提高了执行效率。缺点是递归以及可能存在较大的空间复杂度。

public class Solution {

    public int fibonacci(int n) {
        if (n == 1 || n == 2) return n - 1;

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

上述迭代执行利用了动态规划的思想，自底向上求解，类似的还有Climbing Stairs

Time complexity: O(n) Space complexity: O(n)

实际上我们只在乎最近的两个数，我们实际上不需要存储所有的数，所以我们可以讲space 从O(n) 降为O(1)

public class Solution {

    public int fibonacci(int n) {
        if (n == 1 || n == 2) return n - 1;

        int a = 0, b = 1, c = 0;
        for (int i = 2; i < n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

House Robber

掌握DP问题的思考和讲解的过程

  • 第一种适合搜索类的问题(先实现搜索，再从memorization入手)，
  • 第二种DP分析问题的方法，我们可以先考虑下最简单的情况，然后一点点推进，最后得出这是一个DP问题，DP特点入手(optimal substructure, overlap subproblem)

A natural way to approach this problem is to work on the simplest case first. At first, we 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 casen = 1, clearlyf(1) = A1.

Now, let us look atn = 2, whichf(2) = max(A1, A2).

Forn = 3, you have basically the following two options:

  1. Rob the third house, and add its amount to the first house's amount.

  2. 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 asf(–1) =f(0) = 0, which will greatly simplify our code as you can see.

The answer will be calculated asf(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. Time complexity: O(n), Space complexity: O(1)

public long rob(int[] num) {
    int n = A.length;
    if(n == 0)
        return 0;
    long []res = new long[n+1];

    res[0] = 0;
    res[1] = A[0];
    for(int i = 2; i <= n; i++) {
        res[i] = Math.max(res[i-1], res[i-2] + A[i-1]);
    }
    return res[n];
}

or we can use modular operation to simplify our program further. note, I prefer to module 3 since it is easier to analyze.

class Solution {
    public int rob(int[] nums) {
        int n = A.length;
        if(n == 0)
            return 0;
        long []res = new long[3];


        res[0] = 0;
        res[1] = A[0];
        for(int i = 2; i <= n; i++) {
            res[i%3] = Math.max(res[(i-1)%3], res[(i-2)%3] + A[i-1]);
        }
        return res[n%3];
    }
}

House Robber 2

数组变成环形之后，就需要考虑首尾相接的问题了~理论上说，对于长度为n的环 形数组，我们现在有了n种不同的切分方式，去处理长度为n的线性数组。不过我们不需要考虑所有的可能切分，因为只有相邻元素之间会 出现问题。我们只需要把环形数组拆分成两个头尾不同的size = n - 1的subproblems就可以了:

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        // f(2, 3)
        // f(3, 2)
        // return max(f(2, 3), f(3, 2))
        int n = nums.length;
        return Math.max(f(nums, 0, n - 2), f(nums, 1, n - 1));
    }

    private int f(int[] nums, int start, int end) {
        if (end == start) return nums[start];

        // f(k) = max(f(k - 2) + Ak, f(k - 1))
        int n = end - start + 1; // 3 
        int[] dp = new int[n + 1];   // length = 4
        dp[0] = 0;
        dp[1] = nums[start];
        for (int i = 2; i <= n; ++i) {
            dp[i] = Math.max(dp[i - 2] + nums[start + i - 1], dp[i - 1]);
        }
        return dp[n];
    }
}

House Robber 3

At first glance, the problem exhibits the feature of “optimal substructure”: if we want to rob maximum amount of money from current binary tree (rooted atroot), we surely hope that we can do the same to its left and right subtrees.

So going along this line, let’s define the functionrob(root)which will return the maximum amount of money that we can rob for the binary tree rooted atroot; the key now is to construct the solution to the original problem from solutions to its subproblems, i.e., how to getrob(root)fromrob(root.left), rob(root.right), ...etc.

所以对于这样一个recursive solution. And for recursion, it’s always worthwhile figuring out the following two properties:

  • Termination condition

    • when the tree is empty – we’ve got nothing to rob so the amount of money is zero.

  • Recurrence relation

    • how to getrob(root)fromrob(root.left), rob(root.right), ...etc. 也就是说，如果root被rob了，那么the next level of subtrees that are available would be the four “grandchild-subtrees” (root.left.left, root.left.right, root.right.left, root.right.right). 而如果root不rob，那么the next level of available subtrees would just be the two “child-subtrees” (root.left, root.right). We only need to choose the scenario which yields the larger amount of money.

dfs时间复杂度已经是O(n) , n = # of nodes

class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return robTree(root, new HashMap<TreeNode, Integer>());
    }

    private int robTree(TreeNode root, Map<TreeNode, Integer> map) {
        // base case
        if (root == null) return 0;
        if (map.containsKey(root)) return map.get(root);

        // recursive case
        int val = 0;     // the sum of the money it can collect from its grand child like node 4, 5, 6, 7

        if (root.left != null) {
            val += robTree(root.left.left, map) + robTree(root.left.right, map);
        }

        if (root.right != null) {
            val += robTree(root.right.left, map) + robTree(root.right.right, map);
        }

        int ans = Math.max(root.val + val, robTree(root.left, map) + robTree(root.right, map));

        map.put(root, ans);

        return ans;
    }
}

Solution 2:

Ask why we have overlapping subproblems. If you trace all the way back to the beginning, you’ll find the answer lies in the way how we have definedrob(root). As I mentioned, for each tree root, there are two scenarios: it is robbed or is not.rob(root)does not distinguish between these two cases, so “information is lost as the recursion goes deeper and deeper”, which results in repeated subproblems.

If we were able to maintain the information about the two scenarios for each tree root, let’s see how it plays out. Redefinerob(root)as a new function which will return an array of two elements, the first element of which denotes the maximum amount of money that can be robbed ifrootis not robbed, while the second element signifies the maximum amount of money robbed if it is robbed.

public int rob(TreeNode root) {
    int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}

private int[] robSub(TreeNode root) {
    if (root == null) return new int[2];

    int[] left = robSub(root.left);
    int[] right = robSub(root.right);
    int[] res = new int[2];

    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);  // rob(root.left) + rob(root.right)
    res[1] = root.val + left[0] + right[0];

    return res;
}

Jump Game

  • 坐标型
  • 好题，有多种方法，关键在于如何在interview中讲清楚

naive method: using DFS recursive method.

Basic idea is that we try every single jump pattern that takes us from the first position to the last. We start from the first position and jump to every index that is reachable. We repeat the process until last index is reached. When stuck, backtrack.

class Solution {
    public boolean canJump(int[] nums) {
        // the index in nums array is either a good index or a bad index
        return jump(nums, 0);
    }

    private boolean jump(int[] nums, int index) {
        if (index >= nums.length) return false;
        if (index == nums.length - 1) {
            return true;
        }

        int step = nums[index];
        for (int i = 1; i <= step; ++i) {   // pay attention to: can improve by traversing from right to left.
            if (jump(nums, index + i)) {
                return true;
            }
        }
        return false;
    }
}

Time is O(2^(n)) using induction when required proof. Space is O(n)

Dynamic Programming Top-down

in this method, we can use 1D array to store the intermediate result, which would be used later. Since the original value for the array is 0, so we define 2 as jump "true" and 1 as jump "false".

class Solution {
    public boolean canJump(int[] nums) {
        // the index in nums array is either a good index or a bad index
        return jump(nums, 0, new int[nums.length]);
    }

    private boolean jump(int[] nums, int index, int[] arr) {
        if (index >= nums.length) return false;
        if (index == nums.length - 1) {
            return true;
        }

        if (arr[index] > 0) {
            return arr[index] == 2 ? true : false;
        }

        boolean flag = false;
        int step = nums[index];
        for (int i = 1; i <= step; ++i) {
            if (jump(nums, index + i, arr)) {
                flag = true;
            }
        }
        arr[index] = flag == true ? 2 : 1;
        return flag;
    }
}

in this case, Time complexity is O(n^2) and Space complexity is O(2n) where the first n originates from recursion. Second n comes from the usage of the memo table.

Dynamic Programming Bottom-up

The description of the question tells us: If one index cannot be reached, all the latter indexes cannot be reached. Since of that, what should be done is very simple, track the max index you can reach.

class Solution {
    public boolean canJump(int[] nums) {

        if (nums == null || nums.length == 0) return false;
        int maxReach = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if ( i > maxReach ) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

Greedy

the basic idea is that Iterating right-to-left, for each position we check if there is a potential jump that reaches a _GOOD _index (

currPosition + nums[currPosition] >= leftmostGoodIndex). If we can reach a GOOD _index, then our position is itself _GOOD.

Also, this new _GOOD _position will be the new leftmost _GOOD _index. Iteration continues until the beginning of the array. If first

position is a _GOOD _index then we can reach the last index from the first position.

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

Time: O(n), Space: O(1)

Jump Game 2

Your goal is to reach the last index in the minimum number of jumps.

State: f[i] 从起点跳到这个位置最少需要多少步

Function: f[i] = MIN(f[j]+1, j < i && j + A[j] >= i) 取出所有能从j到i中的最小值

Initialization: f[0] = 0，即一个元素时不需移位即可到达

Answer: f[n-1]

// version 1: Dynamic Programming
// 这个方法，复杂度是 O(n^2)，会超时，但是依然需要掌握。
public class Solution {
    public int jump(int[] A) {
        // state
        int[] steps = new int[A.length];

        // initialize
        steps[0] = 0;
        for (int i = 1; i < A.length; i++) {
            steps[i] = Integer.MAX_VALUE;
        }
        // function
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) {
                    steps[i] = Math.min(steps[i], steps[j] + 1);
                }
            }
        }
        // answer
        return steps[A.length - 1];
    }
}

Greedy algorithm

time complexity is O(n), and space complexity is O(1).

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int res = 0;
        int curMaxArea = 0;
        int maxNext = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            maxNext = Math.max(maxNext, i + nums[i]);
            if (i == curMaxArea) {
                res++;
                curMaxArea = maxNext;
            }
        }
        return res;
    }
}

Decode Ways

  • 坐标型

分析:

climbing stairs的变种，区别是climb stairs中，f[n] = f[n-1] + f[n-2]，这个关系的成立是不需要条件的。这道题也存在这种关系，但成立是需要条件来判断的。

state: f[i] 表示前i个数字有几种decode方式

function: f[n] = f[n-1] + f[n-2]，其中满足使用f[n-1]的条件是在n-1位置上的数字不为0，满足使用f[n-2]的条件是前n-2~n所组成的数字在(10, 26]。

initialize: f[0] = 1, f[1] = 1

answer: f[-1]

class Solution:
    def numDecodings(self, s):
        if not s or s[0] == '0':
            return 0

        f = [1, 1]
        for i in range(2, len(s)+1):
            if s[i-1] != '0' and 10 < int(s[i-2:i]) <= 26:  
                f.append(f[i-1]+f[i-2])

            elif s[i-1] != '0':
                f.append(f[i-1])

            elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
                f.append(f[i-2])

            else:
                return 0

        return f[-1]

Word Break

  • 序列型

如果不是跟坐标相关的动态规划，一般有N个数/字符，就开N+1个位置的数组，第0个位置留出来做初始化。

分析：

state: f[i]表示前i个字符是否可被完美切割

function: f[i] = OR{f[j]} 其中任意j < i，且j+1~i是一个word in dict

initialize: f[0] = True

answer: f[n]

class Solution:
    def wordBreak(self, s, dict):
        if len(dict) == 0:
            return len(s) == 0

        n = len(s)
        f = [False] * (n+1)
        f[0] = True

        maxLength = max([len(w) for w in dict])
        for i in range(1, n+1):
            for j in range(1, min(i, maxLength) + 1): #avoid exceed time limit, 大于maxLength时就不用继续搜索dict 
                if f[i-j] and s[i-j:i] in dict:
                    f[i] = True
                    break

        return f[n]

results matching ""

    No results matching ""