LC64 Minimum Path Sum

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

1
2
3
4
5
6
7
8
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
Think

DP，直接在原数组上修改即可，grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minPathSum(vector<vector<int>>& grid) {
    if(grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    for(int i = 1; i < m; i++){
        grid[i][0] += grid[i - 1][0];
    }
    for(int i = 1; i < n; i++){
        grid[0][i] += grid[0][i - 1];
    }
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
        }
    }
    return grid.back().back();
}

LC70 Climbing Stairs

Problem

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?

Note: Given n will be a positive integer.

Example 1:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: 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
Think
  • Approach 1

DP，类似斐波那契数列即可，注意要使用long作为数据结构

  • Approach 2

由于我们可以知道这题就是求解斐波那契数列的第n项，因此有矩阵Q=[Fn+1FnFnFn−1]Q=\begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix}

初始值Q0=[1110]Q_0=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}，则Q0n{Q_0}^n的左上角的值即为我们要求的结果。

为减小计算次数，我们采用二分的方法进行计算，如果为奇数，则先计算B=A∗qB=A*q，再计算B∗BB*B

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
int climbStairs(int n) {
    long dp0 = 1, dp1 = 1;
    while(n--){
        int tmp = dp1;
        dp1 = dp0 + dp1;
        dp0 = tmp;
    }
    return static_cast<int>(dp0);
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int climbStairs(int n) {
    vector<vector<long>> q = {{1, 1}, {1, 0}};
    vector<vector<long>> res = power(q, n);
    return static_cast<int>(res[0][0]);
}
vector<vector<long>> power(vector<vector<long>> q, int n){
    vector<vector<long>> res = {{1, 0}, {0, 1}};
    while(n > 0){
        if ((n & 1) == 1) {
            res = multi(res, q);
        }
        n >>= 1;
        q = multi(q, q);
    }
    return res;
}

vector<vector<long>> multi(vector<vector<long>> a, vector<vector<long>> b){
    vector<vector<long>> res = {{1, 0}, {0, 1}};
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            res[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
        }
    }
    return res;
}

LC72 Edit Distance

Problem

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

1
2
3
4
5
6
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

1
2
3
4
5
6
7
8
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
Think

DP，dp[i, j]表示长度为i的字符串word1和长度为j的字符串word2的编辑距离；

如果word1[i - 1] == word2[j - 1]，则dp[i, j] = dp[i - 1, j - 1];

否则，dp[i, j] = 1 + min(dp[i - 1, j - 1], min(dp[i - 1, j], dp[i, j - 1]));

初始条件：

dp[i, 0] = i; 对0 <= i <= m;

dp[0, i] = i; 对0 <= i <= n;

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for(int i = 0; i <= m; i++){
        dp[i][0] = i;
    }
    for(int i = 0; i <= n; i++){
        dp[0][i] = i;
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(word1[i - 1] == word2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[m][n];
}

LC87 Scramble String

Problem

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

1
2
3
4
5
6
7
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

1
2
3
4
5
6
7
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

1
2
3
4
5
6
7
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

1
2
Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

1
2
Input: s1 = "abcde", s2 = "caebd"
Output: false
Think
  • Approach 1

递归

s1[0, i - 1]和s2[0, i - 1]满足scramble，且s1[i, n - 1]和s2[i, n - 1]满足scramble；

s1[0, i - 1]和s2[n - i, n - 1]满足scramble，且s1[i, n - 1]和s2[0, n - i - 1]满足scramble；

  • Approach 2

DP，设三维数组dp[i, j, len]表示s1[i…i + len - 1]和s2[j…j + len - 1]是否scramble

则有当len == 1时，dp[i, j, 1] = s1[i] == s2[j]；

否则，判断是否可以将s1和s2分别分割成两段，使得这两段互相可以scramble，即：

dp[i, j, len] = || ((dp[i + k, j + k, len - k] && dp[i, j, k]) || (dp[i, j + len - k, k] && dp[i + k, j, len - k])), 0 < k < len

即两种情况，一是s1和s2均取前k个字符，再取剩下的len - k个字符；二是s1取前k个字符，和s2取前len - k个字符进行比较，然后s1取剩下的len - k个字符和s2取剩下的k个字符进行比较。

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isScramble(string s1, string s2) {
    if(s1.size() != s2.size()) return false;
    if(s1 == s2) return true;
    string str1 = s1, str2 = s2;
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());
    if(str1 != str2) return false;
    int n = s1.size();
    for(int i = 1; i < n; i++){
        string ss1 = s1.substr(0, i);
        string ss2 = s1.substr(i);
        string ss3 = s2.substr(0, i);
        string ss4 = s2.substr(i);
        if(isScramble(ss1, ss3) && isScramble(ss2, ss4)) return true;
        ss3 = s2.substr(n - i);
        ss4 = s2.substr(0, n - i);
        if(isScramble(ss1, ss3) && isScramble(ss2, ss4)) return true;
    }
    return false;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool isScramble(string s1, string s2) {
    if(s1.size() != s2.size()) return false;
    if(s1 == s2) return true;
    string str1 = s1, str2 = s2;
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());
    if(str1 != str2) return false;
    int n = s1.size();
    vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(n + 1, false)));
    for(int len = 1; len <= n; len++){
        for(int i = 0; i <= n - len; i++){
            for(int j = 0; j <= n - len; j++){
                if(len == 1) dp[i][j][len] = (s1[i] == s2[j]);
                else{
                    for(int k = 1; k < len; k++){
                        if((dp[i + k][j + k][len - k] && dp[i][j][k]) || (dp[i][j + len - k][k] && dp[i + k][j][len - k])){
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
    }
    return dp[0][0][n];
}

LC91 Decode Ways

Problem

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

1
2
3
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

1
2
3
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Think

DP，dp[i]表示s中前i个字符构成的字符串能组成多少个结果

如果s[i - 1]可以被翻译成字母，则dp[i] += dp[i - 1];

如果s[i - 1, i]可以被翻译成字母，则dp[i] += dp[i - 2];

初始条件为dp[0] = 1, dp[1] 为s[0]是否可以翻译成字母。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool isValid(string s){
    if(s.size() > 2) return false;
    if(s.size() == 1){
        return s[0] >= '1' && s[0] <= '9';
    }
    else{
        if(s[0] == '1'){
            return s[1] >= '0' && s[1] <= '9';
        }
        else if(s[0] == '2'){
            return s[1] >= '0' && s[1] <= '6';
        }
        else{
            return false;
        }
    }
}
int numDecodings(string s) {
    int n = s.size();
    if(n == 0) return 0;
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = isValid(s.substr(0, 1)) ? 1 : 0;
    if(n == 1) return dp[1];
    
    for(int i = 2; i <= n; i++){
        if(isValid(s.substr(i - 1, 1)))
            dp[i] += dp[i - 1];
        if(isValid(s.substr(i - 2, 2))){
            dp[i] += dp[i - 2];
        }
    }
    return dp.back();
}

LC97 Interleaving String

Problem

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Think

DP，使用二维数组dp[i, j]表示长度为i的s1和长度为j的s2能否组成s3；

dp[i, j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1, j]) || (s2[j - 1] == s3[i + j - 1] && dp[i, j - 1]);

初始条件即为s1和s2分别为0的时候

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isInterleave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if(s3.size() != m + n) return false;
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for(int i = 1; i <= m; i++){
        dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
    }
    for(int i = 1; i <= n; i++){
        dp[0][i] = dp[0][i - 1] && s2[i - 1] == s3[i - 1];
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);
        }
    }
    return dp[m][n];

LC115 Distinct Subsequences

Problem

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It’s guaranteed the answer fits on a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^
Think

DP，dp[i ,j]表示从后往前长度分别为m-i和n-j的字符串所能匹配出来的数目；

dp[i, j] = dp[i + 1, j] + dp[i + 1, j + 1] * (s[i] == t[j])

注意初始条件是从右下角开始的，因此需要先设置所有的dp[i, n]和dp[m, j]；

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    if(m < n) return 0;
    vector<vector<long>> dp(m + 1, vector<long>(n + 1, 0));
    dp[m][n] = 1;
    for(int i = m - 1; i >= 0; i--){
        dp[i][n] = 1;
    }
    for(int i = n - 1; i >= 0; i--){
        dp[m][i] = 0;
    }
    for(int i = m - 1; i >= 0; i--){
        for(int j = n - 1; j >= 0; j--){
            dp[i][j] = dp[i + 1][j];
            if(s[i] == t[j]){
                dp[i][j] += dp[i + 1][j + 1];
            }
        }
    }
    return (int)dp[0][0];
}

LC120 Triangle

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Think

DP，dp[i, j]表示到达第i行第j列的时候的最短路径，则有

dp[i,j]={dp[i−1][j]+triangle[i][j],j=0dp[i−1][j−1]+triangle[i][j],j=imin(triangle[i−1][j],triangle[i−1][j−1])+triangle[i][j],otherwisedp[i, j] =\begin{cases}dp[i - 1][j] + triangle[i][j], j = 0\\dp[i - 1][j - 1] + triangle[i][j], j = i\\min(triangle[i - 1][j], triangle[i - 1][j - 1]) + triangle[i][j], otherwise\end{cases}

可以直接用triangle数组来代替dp数组

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.back().size();
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0){
                triangle[i][j] = triangle[i - 1][j] + triangle[i][j];
            }
            else if(j == i){
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];
            }
            else{
                triangle[i][j] = min(triangle[i - 1][j] + triangle[i][j], triangle[i - 1][j - 1] + triangle[i][j]);
            }
        }
    }
    int res = INT_MAX;
    for(int i = 0; i < n; i++){
        res = min(res, triangle.back()[i]);
    }
    return res;
}

LC139 Word Break

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

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

Example 2:

1
2
3
4
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:

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

DP，设dp[i]表示长度为i的字符串s能否满足条件，则有：

dp[i] = dp[j] && isWord(s.substr(j, i - j)), for 0 <= j <= i - 1，注意这里只要有一个j满足要求，则dp[i]就等于true

isWord函数可以用哈希表来代替

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.size();
    vector<bool> dp(n + 1, false);
    unordered_map<string, int> m;
    for(string str: wordDict){
        m[str] = 1;
    }
    dp[0] = true;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i - 1; j++){
            if(dp[j] && m.count(s.substr(j, i - j))){
                dp[i] = true;
                break;
            }
        }
    }
    return dp.back();
}

LC140 Word Break II

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

1
2
3
4
5
6
7
8
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

1
2
3
4
5
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
Think

DFS，带记忆数组

DP会超时

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_map<string, vector<string>> m;
    return helper(s, wordDict, m);
}
vector<string> helper(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& m){
    if(m.count(s)) return m[s];
    if(s.empty()){
        return {""};
    }
    vector<string> res;
    for(auto word: wordDict){
        if(s.substr(0, word.size()) == word){
            vector<string> tmp = helper(s.substr(word.size()), wordDict, m);
            for(auto str: tmp){
                res.push_back(word + (str == "" ? "" : " ") + str);
            }
        }
    }
    m[s] = res;
    return res;
}

LC152 Maximum Product Subarray

Problem

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

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

Example 2:

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

DP，分别计算[0, i]的最大累乘值和最小累乘值，因为可能有负数，所以最大值和最小值都有可能在下一次变成最小值和最大值，因此两个都需要计算。

Code 
1
2
3
4
5
6
7
8
9
10
11
int maxProduct(vector<int>& nums) {
    int n = nums.size(), res = nums[0];
    int minValue = 1, maxValue = 1;
    for(auto num: nums){
        int tmp1 = minValue, tmp2 = maxValue;
        minValue = min(num, min(num * tmp1, num * tmp2));
        maxValue = max(num, max(num * tmp1, num * tmp2));
        res = max(res, maxValue);
    }
    return res;
}

LC174 Dungeon Game

Problem

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K) -3 3
-5 -10 1
10 30 -5 §

Note:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
Think

DP，设dp[i, j]表示在(i, j)这个位置出发，到最右下角所需要的最小生命值。从这个点出发有两种可以走的路径：

一是向右，即有health1 = max(1, dp[i, j + 1] - dungeon[i, j])

二是向下，即有health2 = max(1, dp[i + 1, j] - dungeon[i, j])

注意此处首先要判断能不能向右或者向下走，其次要注意与比较大小，如果比1大则说明需要更多的生命值，如果比1小，则说明就算在这个地方没有生命值了也可以继续走到最后，但是由于在每个点处至少要有1点生命值，因此至少要为1；

然后取两者里较小的那一个赋给dp[i, j]，此处需要判断，如果求出来的值为INT_MAX，则说明这一个点处既不可以向右也不可以向下，也就是最右下角的那一个点，需要单独求值。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
    for(int i = m - 1; i >= 0; i--){
        for(int j = n - 1; j >= 0; j--){
            int rightHealth = INT_MAX, downHealth = INT_MAX;
            if(j != n - 1){
                rightHealth = max(1, dp[i][j + 1] - dungeon[i][j]);
            }
            if(i != m - 1){
                downHealth = max(1, dp[i + 1][j] - dungeon[i][j]);
            }
            int nextHealth = min(rightHealth, downHealth);
            if(nextHealth == INT_MAX){
                dp[i][j] = (dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j]);
            }
            else{
                dp[i][j] = nextHealth;
            }
        }
    }
    return dp[0][0];
}

LC213 House Robber II

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, 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:

1
2
3
4
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

1
2
3
4
Input: [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.
Think

DP，分两种情况，一种是只偷0 - n-2户，一种是只偷1 - n-1户的，最后比较终值。

注意特殊情况。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int rob(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) return 0;
    if(n == 1) return nums[0];
    if(n == 2) return max(nums[0], nums[1]);
    vector<int> dp1(n, 0), dp2(n, 0);
    dp1[0] = nums[0];
    dp1[1] = max(nums[0], nums[1]);
    dp1[2] = max(dp1[1], dp1[0] + nums[2]);
    dp2[1] = nums[1];
    dp2[2] = max(nums[1], nums[2]);

    for(int i = 2; i < n - 1; i++){
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
    }
    dp2[n - 1] = max(dp2[n - 2], dp2[n - 3] + nums[n - 1]);
    return max(dp1[n - 2], dp2[n - 1]);
}

LC221 Maximal Square

Problem

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

1
2
3
4
5
6
7
8
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4
Think

DP，二维数组dp[i, j]表示以在(i, j)处的点为右下角的点的时候的最大边长，则有

dp[i, j] = min(dp[i, j - 1], dp[i - 1, j], dp[i - 1, j - 1]) + 1, if matrix[i, j] == 1

可以简化成一维数组的DP

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maximalSquare(vector<vector<char>>& matrix) {
    if(matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    int res = 0;
    vector<int> dp(n, 0);
    
    for(int i = 0; i < m; i++){
        int pre = dp[0];
        dp[0] = matrix[i][0] == '1' ? 1: 0;
        res = max(res, dp[0]);
        for(int j = 1; j < n; j++){
            int tmp = dp[j];
            if(matrix[i][j] == '1'){
                dp[j] = min(pre, min(dp[j], dp[j - 1])) + 1;
                res = max(res, dp[j]);
            }
            else{
                dp[j] = 0;
            }
            pre = tmp;
        }
    }
    return res * res;
}

LC264 Ugly Number II

Problem

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

1
2
3
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

  1. 1 is typically treated as an ugly number.
  2. n does not exceed 1690.
Think

类似三指针和堆结合的做法，相当于每一次取2 3 5对应的倍数堆里的最小值

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
int nthUglyNumber(int n) {
    vector<int> dp(n, 0);
    dp[0] = 1;
    int res, i2 = 0, i3 = 0, i5 = 0;
    for(int i = 1; i < n; i++){
        res = min(dp[i2] * 2, min(dp[i3] * 3, dp[i5] * 5));
        dp[i] = res;
        if(res == dp[i2] * 2) i2++;
        if(res == dp[i3] * 3) i3++;
        if(res == dp[i5] * 5) i5++;
    }
    return dp.back();
}

Review

  1. DP的方向性，想不出来的时候可以从前后两个方向去考虑（二维数组则是四个角落的方向）；
  2. DP数组中的参数有的时候会采用原数组的下标，而有的时候会使用长度作为变量，而且大多数时候是用在字符串相关的问题中；
  3. DP数组的状态转化的时候有可能会需要遍历[0, i - 1]或者[i + 1, n - 1]的部分取寻找符合要求的子数组；