Ref: link

Fibonacci formula: F(n) = F(n-1) + F(n-2). F(0) = 0. F(1) = 1. F(2) = 1.

70. Climbing Stairs (Easy)

A very easy problem. The formula of dp is dp[i] = dp[i-1] + dp[i-2]. For the nth stair, we have two ways to arrive there. One way is use 1 step from the (n-1)th stair. The other way is use 2 steps from the (n-2)th stair. Therefore, all ways to the nth stair is the sum of all ways to the (n-1)th stair and the (n-2)th stair.

Time complexity is O(n). Space complexity is O(n).

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

We can also use Fibonacci number to save more memory. Fibonacci number is F(n) = F(n-1) + F(n-2). The formula is same as this dp formula. Therefore, we don’t need an array to store value. We just need to calculate the value of the nth Fibonacci number.

Time complexity is O(n). Space complexity is O(1). Here is the link.

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

198. House Robber (Easy)

The idea of this problem is pick up some non-adjacent elements and make sure their sum is maximum. dp[i] means the maximum sum between 0 and i. The formula is dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]). dp[0] = nums[0]. dp[1] = Math.max(nums[0],nums[1]). And start iteration from index 2.

We can also save memory by using two variables. These two variables means whether we rob current house. If the position of current house id odd number, we compare the value of even and the value of previous odd plus current house. ‘odd’ variable doesn’t mean we only rob odd positions. It means the house we currently rob is at odd position.

Time complexity is O(n). Space complexity is O(1). Here is the link.

public int rob(int[] nums) {
    int odd = 0;
    int even = 0;
    for(int i =0;i<nums.length;i++){
        if(i%2==0)
            even = Math.max(even+nums[i],odd);
        else
            odd = Math.max(odd+nums[i],even);
    }
    return Math.max(even,odd);
}

213. House Robber II (Medium)

This problem is same as the previous problem. The only difference is all houses at this place are arranged in a circle. This means we cannot rob the first house and last house at the same time. The easiest way is to use previous function and consider to rob between [0,nums.length-1] and [1,nums.length] separately. Get the larger value as the answer.

Time complexity is O(n). Space complexity is O(1). Here is the link.

public int rob(int[] nums) {
    if(nums.length==1)return nums[0];
    if(nums.length==0)return 0;
    return Math.max(robpart(nums,0,nums.length-1),robpart(nums,1,nums.length));
}

public int robpart(int[]nums,int start,int end){
    int odd = 0;
    int even = 0;
    for(int i =start;i<end;i++){
        if(i%2==0)
            even = Math.max(even+nums[i],odd);
        else
            odd = Math.max(odd+nums[i],even);
    }
    return Math.max(even,odd);
}

634. Find the Derangement of An Array

Ref: https://www.cnblogs.com/grandyang/p/7210929.html

This problem is difficult because the dp formula is not easy to get. For example, n = 4.

  1. We put number 4 at the position k = 3. Now, it becomes [X X 4 X].

  2. Assume 3 is at the position k = 4. Now, it becomes [X X 4 3]. Then, we need to find out how to fill in first 2 positions with number 1 and 2. The answer is same as n = 2. For n = 2, we need to find the number of derangement with 1 and 2.

  3. Assume 3 is not at the position k = 4, so 3 can be only put at first two positions. This situation is same as n = 3. For n = 3, we cannot put 3 at the last position which is same as this situation.

  4. We know 4 has 3 possible positions. Therefore, dp[4] = 3 * (dp[3] + dp[2])

  5. Our dp formula is dp[i] = (i-1)* (dp[i-1]+dp[i-2]). For number n, we can put number n at (n-1) positions. If we put number n at the position k, number k can be put at the position n or not. If number k is put at the position k, the situation is same as n-2. Otherwise, the situation is same as n-1.

Time complexity is O(n). Space complexity can be optimized to O(1). We only need two values dp[i-1] and dp[i-2]. We can use two variable to represent them. Here is the link.

int findDerangement(int n) {
    if (n < 2) return 0;
    vector<long long> dp(n + 1, 0);
    dp[1] = 0; dp[2] = 1;
    for (int i = 3; i <= n; ++i) {
        dp[i] = (dp[i - 1] + dp[i - 2]) * (i - 1) % 1000000007;
    }
    return dp[n];
}

91. Decode Ways

At first, let’s not consider about the edge case which includes value ‘0’. Assume the input string doesn’t have value ‘0’. dp[i] means the total number of ways to decode it. Assume the current index is k. If s[k-1]s[k] is not in the mapping, we can only decode these two numbers as two separate integers. This means dp[k] = dp[k-1]. If s[k-1][k] is in the mapping, we can decode s[k] in two ways: decode as s[k-1]s[k] or s[k]. If we decode it as s[k-1][k], there are dp[k-2] solutions. If we decode it as s[k], there are dp[k-1] solutions. The total number of ways to decode it is dp[k] = dp[k-1]+dp[k-2]. Therefore, our dp function is

dp[i] = dp[i-1] + dp[i-2],  10 <= number <= 26 

dp[i] = dp[i-1], Otherwise

Now, let’s consider about value ‘0’. Assume that the kth value is ‘0’. And (k-1)th value is ‘1’ or ‘2’. In this situation, we can only decode them as s[k-1]s[k]. This is the only valid way to decode these two values. Therefore, dp[k] = dp[k-1]. But if (k-1)th value is other values. We cannot find a way to decode value ‘0’. Value ‘0’ cannot exits alone and it cannot be decoded with its previous value. This means the whole input string cannot be decoded. We return 0.

dp[i] = dp[i-1] 10 <= number <= 26 

answer = 0 Otherwise

I thinks this problem is in the category of Fibonacci, because dp function is dp[i] = dp[i-1] +dp[i-2] under some situation. We only need previous two values, so we can use two variables to represent the whole dp array. ‘first’ represents dp[i-2]. ‘second’ represents dp[i-1]. Meanwhile, we need to check the value of index i. If value is ‘0’, we assign ‘0’ to variable ‘second’. dp[i] includes dp[i-1] no matter what the situation, we can keep the value of ‘second’ as the current value. If s[i-1][i] is valid, we plus the value of ‘first’. Otherwise, we update the value of ‘first’ to the value of ‘second’.

Time complexity is O(1). Space complexity is O(1). Here is the link.

public int numDecodings(String s) {
    if(s.length()==0||s.charAt(0)=='0')return 0;
    int first = 1; // represent dp[i-2]
    int second = 1; // represent dp[i-1]
    for(int i = 1;i<s.length();i++){
        second = s.charAt(i)=='0'?0:second;
        if(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)<'7')){
            second+=first;
            first = second-first;
        }
        else{
            first = second;
        }
    }
    return second;
}