LeetCode-dp类总结

算法 评论

本文主要是对leetcode中的dp类算法的总结，包含了各题的solution和常用的解决方法。

相关源码：code

198. House Robber

Description:

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.

解题思路：此题是动态规划中的经典问题，此题有个限制相邻两个房间不能同时被盗，那么最优子结构就是cur=max(pre+nums[i], cur)，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
int rob(vector<int> &nums)
{
    int n=nums.size();
    int pre=cur=0;
    for(int i=0; i<n; i++)
    {
        int temp = max(pre+nums[i], cur);
        pre = cur;
        cur = temp;
    }
    return cur;
}

740. Delete and Earn

Description:

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

1
2
3
4
5
6
Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

1
2
3
4
5
6
7
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.

Each element nums[i] is an integer in the range [1, 10000].

解题思路：此题本质上是house robber问题，参考上题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> hash(10001,0);
        for(int n :nums)
            hash[n]+=n;
        int pre=0, cur=0;
        for(int i=0; i<10001; i++){
            int temp=cur;
            cur=max(pre+hash[i],cur);
            pre=temp;
        }
        return cur;
    }
};

64. Minimum Path Sum

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

1
2
3
4
[[1,3,1],
 [1,5,1],
 [4,2,1]]

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

解题思路：在矩阵上求解从左上角到右下角最短路径，最优子结构关注当前元素的上方元素和左方元素，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> state(m,vector<int>(n, grid[0][0]));
        for(int i=1; i<m; i++)
            state[i][0] = state[i-1][0]+grid[i][0];
        for(int j=1; j<n; j++)
            state[0][j] = state[0][j-1]+grid[0][j];
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                state[i][j] = min(state[i-1][j], state[i][j-1]) + grid[i][j];
            }
        }
        return state[m-1][n-1];
    }
};

712. Minimum ASCII Delete Sum for Two Strings

Description:

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

1
2
3
4
5
6
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

1
2
3
4
5
6
7
Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.

All elements of each string will have an ASCII value in [97, 122].

解题思路：本题算是dp中一类经典题“字符串匹配”，利用矩阵解题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m=s1.size(), n=s2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int j=1; j<=n; j++)
            dp[0][j]=dp[0][j-1]+s2[j-1];
        for(int i=1; i<=m; i++){
            dp[i][0] = dp[i-1][0]+s1[i-1];
            for(int j=1; j<=n; j++){
                if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j]+s1[i-1],dp[i][j-1]+s2[j-1]);
            }
        }
        return dp[m][n];
    }
};

647. Palindromic Substrings

Description:

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

1
2
3
4
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3
4
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won’t exceed 1000.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countSubstrings(string s) {
        int res = 0, n = s.length();
        for(int i = 0; i < n; i++){
            for(int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++)res++;
            for(int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++)res++;
        }
        return res;
    }
};

467. Unique Substrings in Wraparound String

Description:

Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

1
2
3
4
5
Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

1
2
3
4
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

1
2
3
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector<int> count(26);
        int maxLenCur=0;
        for(int i=0; i<p.size(); i++){
            if(i>0 && (p[i]-p[i-1]==1 || p[i-1]-p[i]==25)){
                maxLenCur++;
            }else{
                maxLenCur=1;
            }
            
            int index=p[i]-'a';
            count[index]=max(count[index],maxLenCur);
        }
        int sum=0;
        for(int n : count) sum+=n;
        return sum;
    }
};

95. Unique Binary Search Trees II

Description:

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

代码如下：

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
class Solution{
public:
    vector<TreeNode*> generateTrees(int n){
        if(n==0) return vector<TreeNode*> {NULL};
        return generator(1, n);
    }
  	
    vector<TreeNode*> generator(int start, int end){
        if(start>end) return vector<TreeNode*> {NULL};
        vector<TreeNode*> res;
        for(int i=start; i<=end; i++){
            vector<TreeNode*> l = generator(start, i-1);
            vector<TreeNOde*> r = generator(i+1, end);
            for(int j=0; j<l.size();j++){
                for(int k=0; k<r.size();k++){
                    TreeNode* root = new TreeNode(i);
                  	root->left = l[j];
                    root->right = r[k];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
}

96. Unique Binary Search Trees

Description:

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numTrees(int n) {
        vector<int> res(n+1);
        res[0]=res[1]=1;
        for(int i=2; i<=n; i++){
            for(int j=1; j<=i; j++){
                res[i]+=res[j-1]*res[i-j];
            }
        }
        return res[n];
    }
};

120. Triangle

Description:

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
7
[
     [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).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> minArr(triangle.back());
        for(int layer=n-2; layer>=0; layer--){
            for(int i=0; i<=layer;i++){
                minArr[i]=min(minArr[i],minArr[i+1]) + triangle[layer][i];
            }
        }
        return minArr[0];
    }
};

650. 2 Keys Keyboard

Description:

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

  1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
  2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:

1
2
3
4
5
6
7
8
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

  1. The n will be in the range [1, 1000].

代码如下：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minSteps(int n) {
        if(n==1) return 0;
        for(int i=2; i<n; i++)
            if(n%i==0) return i+minSteps(n/i);
        return n;
    }
};

474. Ones and Zeros

Description:

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:

  1. The given numbers of 0s and 1s will both not exceed 100
  2. The size of given string array won’t exceed 600.

Example 1:

1
2
3
4
5
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

1
2
3
4
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2

Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

解题思路：此题明显是一道dp题，本题适合二维矩阵，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> res(m+1, vector<int>(n+1, 0));
        for(auto &s : strs){
            int cZeros=0, cOnes=0;
            for(auto c : s){
                if(c=='0') cZeros++;
                else if(c=='1') cOnes++;
            }
            
            for(int i=m; i>=cZeros; i--){
                for(int j=n; j>=cOnes; j--){
                    res[i][j]=max(res[i][j], res[i-cZeros][j-cOnes]+1);
                }
            }
        }
        return res[m][n];
    }
};

486. Predict the Winner

Description:

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

1
2
3
4
5
6
7
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.

Example 2:

1
2
3
4
5
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

  1. 1 <= length of the array <= 20.
  2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
  3. If the scores of both players are equal, then player 1 is still the winner.

代码如下：

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
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i=0; i<n; i++) dp[i][i]=nums[i];
        for(int len=1; len<n; len++){
            for(int i=0; i<n-len;i++){
                int j = i+len;
                dp[i][j]=max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]);
            }
        }
        return dp[0][n-1]>=0;
    }
    
    bool PredictTheWinner2(vector<int>& nums) {
        //if(nums==NULL) return true;
        int n = nums.size();
        if((n&1)==0) return true;
        vector<int> dp(n);
        for(int i=n-1; i>=0; i--){
            for(int j=i; j<n;j++){
                if(i==j) dp[i]=nums[i];
                else dp[j]=max(nums[i]-dp[j],nums[j]-dp[j-1]);
            }
        }
        return dp[n-1]>=0;
    }
};

416. Partition Equal Subset Sum

Description:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example 1:

1
2
3
4
5
6
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3
4
5
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

解题思路：本质是dp题，只是套了一层，代码如下：

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
35
36
37
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int num : nums) sum+=num;
        if((sum&1)==1) return false;
        sum /= 2;
        vector<vector<bool>> dp(n+1, vector<bool>(sum+1, false));
        dp[0][0]=true;
        for(int i=1; i<n+1; i++) dp[i][0]=true;
        for(int j=1; j<sum+1; j++) dp[0][j]=false;
        for(int i=1; i<n+1; i++){
            for(int j=1; j<sum+1; j++){
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1]) dp[i][j]=dp[i][j] || dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][sum];
    }
    
    bool canPartition2(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int num : nums) sum+=num;
        if((sum&1)==1) return false;
        sum /= 2;
        vector<bool> dp(sum+1, false);
        dp[0]=true;
        for(int num : nums){
            for(int i=sum; i>=num; i--){
                dp[i]=dp[i]||dp[i-num];
            }
        }
        return dp[sum];
    }
};

494. Target Sum

Description:

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

代码如下：此题套了上一题的dp，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum=0;
        for(int num : nums) sum+=num;
        return sum<S||(S+sum)%2>0?0:subsetSum(nums, (S+sum)>>1);
    }
    int subsetSum(vector<int> &nums, int target){
        vector<int> dp(target+1, 0);
        dp[0]=1;
        for(int num : nums){
            for(int i=target; i>=num; i--) dp[i]+=dp[i-num];
        }
        return dp[target];
    }
};

139. Word Break

Description:

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. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

解题思路：一般我都需要把子字符串都枚举出来，自然而然会想到dp，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(wordDict.size()==0) return false;
        unordered_set<string> dict;
        for(string str : wordDict) dict.insert(str);
        vector<bool> dp(s.size()+1, false);
        dp[0]=true;
        for(int i=1; i<=s.size(); i++){
            for(int j=i-1; j>=0; j--){
                if(dp[j]){
                    string word = s.substr(j,i-j);
                    if(dict.find(word)!=dict.end()){
                        dp[i]=true;
                        break;
                    }
                }
            }
        }
        return dp[s.size()];
    }
};

714. Best Time to Buy and Sell Stock with Transaction Tree

Description:

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

1
2
3
4
5
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        long t_ik0=0, t_ik1=INT_MIN;
        for(int price : prices){
            long t_ik0_old = t_ik0;
            t_ik0 = max(t_ik0, t_ik1+price-fee);
            t_ik1 = max(t_ik1, t_ik0_old-price);
        }
        return t_ik0;
    }
};

152. Maximum Product Subarray

Description:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int pMax=0, nMax=0, m=0;
        for(int i=0; i<n; i++){
            if(nums[i]<0) swap(pMax, nMax);
            pMax=max(pMax*nums[i], nums[i]);
            nMax=min(nMax*nums[i], nums[i]);
            if(pMax>m) m = pMax;
        }
        return m;
    }
};

516. Longest Palindromic Subsequence

Description:

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

1
2
"bbbab"

Output:

1
2
4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

1
2
"cbbd"

Output:

1
2
2

One possible longest palindromic subsequence is “bb”.

解题思路：字符串=>网格，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        if(len==0) return 0;
        vector<vector<int>> dp(len, vector<int>(len,0));
        for(int i=len-1; i>=0; i--){
            dp[i][i]=1;
            for(int j=i+1; j<len; j++){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }
};

221. Maximal Square

Description:

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

For example, given the following matrix:

1
2
3
4
5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

代码如下：

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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(!m) return 0;
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n,0));
        int maxsize=0;
        for(int i=0; i<m; i++) {
            dp[i][0]=matrix[i][0]-'0'; 
            maxsize=max(maxsize,dp[i][0]);
        }
        for(int j=0; j<n; j++) {
            dp[0][j]=matrix[0][j]-'0';
            maxsize=max(maxsize,dp[0][j]);
        }
        for(int i=1; i<m; i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
                    maxsize=max(maxsize,dp[i][j]);
                }
            }
        }
        return maxsize*maxsize;
    }
};

63. Unique Paths II

Description:

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

1
2
3
4
5
6
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

代码如下：

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
35
36
37
38
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size(), n=obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) return 0;
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0]=1;
        for(int i=1; i<m; i++){
            if(obstacleGrid[i][0]==1||dp[i-1][0]==0) dp[i][0]=0;
            else dp[i][0]=1;
        }
        for(int j=1; j<n; j++){
            if(obstacleGrid[0][j]==1||dp[0][j-1]==0) dp[0][j]=0;
            else dp[0][j]=1;
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j]==1) dp[i][j]=0;
                else dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
    
    int uniquePathsWithObstacles2(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size(), n=obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) return 0;
        vector<int> dp(n,0);
        dp[0]=1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(obstacleGrid[i][j]==1) dp[j]=0;
                else if(j>0) dp[j]+=dp[j-1];
            }
        }
        return dp[n-1];
    }
};

264. Ugly Number II

Description:

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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

经典题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int nthUglyNumber(int n) {
        if(n<=0) return 0;
        int t2=0, t3=0, t5=0;
        vector<int> dp(n);
        dp[0]=1;
        for(int i=1; i<n; i++){
            dp[i]=min(dp[t2]*2, min(dp[t3]*3, dp[t5]*5));
            if(dp[t2]*2==dp[i]) t2++;
            if(dp[t3]*3==dp[i]) t3++;
            if(dp[t5]*5==dp[i]) t5++;
        }
        return dp[n-1];
    }
};

115. Distinct Subsequences

Description:

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).

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
17
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
    ^^^

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numDistinct(string s, string t) {
        int m=t.length();
        int n=s.length();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=0; i<=n; i++) dp[0][i]=1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(t[i]==s[j]) dp[i+1][j+1]=dp[i][j]+dp[i+1][j];
                else dp[i+1][j+1]=dp[i+1][j];
            }
        }
        return dp[m][n];
    }
};

140. Word Break II

Description:

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
9
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
11
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:
[]

代码如下：

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
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        
        unordered_set<string> dict;
        unordered_map<int, vector<string>> memo;
        vector<string> output;
        
        for(auto word : wordDict) {
            dict.insert(word);
        }
        
        wordBreakRecur(s, 0, dict, memo);
        
        for(auto str : memo[0])
            output.push_back(str);
        
        return output;
    }
    
    void wordBreakRecur(string& s, int pos, unordered_set<string>& dict, unordered_map<int, vector<string>>& memo)
    {
        string word = "";
        int offset = 0;
        
        while(pos+offset < s.size()) {
            word += s[pos+offset]; 
            
            if(dict.find(word) != dict.end()) {
                if(pos+offset+1 == s.size())
                    memo[pos].push_back(word);
                else {
                    if(memo.find(pos+offset+1) == memo.end())
                        wordBreakRecur(s, pos+offset+1, dict, memo);

                    for(auto str : memo[pos+offset+1]) {
                        memo[pos].push_back(word + " " + str);
                    }            
                }
            }
            offset++;
        }
    }
    
};

174. Dungeon Game

Description:

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 (P)

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.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <vector>

using namespace std;
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> hp(m+1, vector<int>(n+1, INT_MAX));
        hp[m][n-1]=1;
        hp[m-1][n]=1;
        for(int i=m-1;i>=0; i--){
            for(int j=n-1;j>=0;j--){
                int need = min(hp[i+1][j],hp[i][j+1])-dungeon[i][j];
                hp[i][j]=need<=0?1:need;
            }
        }
        return hp[0][0];
    }
};

188. Best Time to Buy and Sell Stock IV

Description:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3
4
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
4
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

解题思路,代码如下：

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
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k >= prices.size()>>1){
            int t_ik0=0, t_ik1=INT_MIN;
            for(int price : prices){
                int t_ik0_old=t_ik0;
                t_ik0=max(t_ik0,t_ik1+price);
                t_ik1=max(t_ik1,t_ik0_old-price);
            }
            return t_ik0;
        }
        vector<int> t_ik0(k+1,0);
        vector<int> t_ik1(k+1,INT_MIN);
        for(int price: prices){
            for(int j=k;j>0;j--){
                t_ik0[j]=max(t_ik0[j],t_ik1[j]+price);
                t_ik1[j]=max(t_ik1[j],t_ik0[j-1]-price);
            }
        }
        return t_ik0[k];
    }
};

279. Perfect Squares

Description:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

1
2
3
Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int numSquares(int n) {
        if(n<=0) return 0;
        vector<int> dp(n+1, INT_MAX);
        dp[0]=0;
        for(int i=1; i<n+1; i++){
            for(int j=1; j*j<=i; j++){
                dp[i]=min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
    
};

32. Longest Valid Parentheses

Description:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
4
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

代码如下：

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
35
36
37
38
39
40
41
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
using namespace std;
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.length(), res = 0;
        stack<int> st;
        for(int i=0; i<len; i++){
            if(s[i]=='(') st.push(i);
            else{
                if(!st.empty() && s[st.top()]=='(') st.pop();
                else st.push(i);
            }
        }
        if(st.empty()) return len;
        int a=len, b=0;
        while(!st.empty()){
            b=st.top();
            st.pop();
            res = max(res, a-b-1);
            a=b;
        }
        res = max(res,a);
        return res;
    }
    
    int longestValidParentheses2(string s) {
        int len = s.length(), res=0;
        vector<int> dp(len, 0);
        for(int i=1;i<len;i++){
            if(s[i]==')' && i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='('){
                dp[i]=dp[i-1] + 2 + ((i-dp[i-1]-2>=0)?dp[i-dp[i-1]-2]:0);
                res = max(dp[i],res);
            }
        }
        return res;
    }
};

62. Unique Paths

Description:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

img
Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

1
2
3
4
5
6
7
8
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

1
2
Input: m = 7, n = 3
Output: 28

代码如下：

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
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n, 0));
        dp[0][0]=1;
        for(int i=1; i<m; i++) dp[i][0]=1;
        for(int j=1; j<n; j++) dp[0][j]=1;
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
    
    int uniquePaths2(int m, int n) {
        vector<int> dp(n,0);
        dp[0]=1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                dp[j]+=dp[j-1];
            }
        }
        return dp[n-1];
    }
};

72. Edit Distance

Description:

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
7
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')

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution { 
public:
    int minDistance(string word1, string word2) { 
        int m = word1.length(), n = word2.length();
        vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;  
        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] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
            }
        }
        return dp[m][n];
    }
};

97. Interleaving String

Description:

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

Example 1:

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

Example 2:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        if(m+n!=s3.length()) return false;
        vector<vector<bool>> dp(m+1, vector<bool>(n+1));
        for(int i=0; i<m+1; i++){
            for(int j=0;j<n+1;j++){
                if(i==0&&j==0) dp[i][j]=true;
                else if(i==0) dp[i][j]=dp[i][j-1] && s2[j-1]==s3[i+j-1];
                else if(j==0) dp[i][j]=dp[i-1][j] && s1[i-1]==s3[i+j-1];
                else dp[i][j]=(dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1]);
            }
        }
        return dp[m][n];
    }
};

ciicA BOCer

个人简介