leetcodeLeetDP

Posted on |

List

题号 题目链接 讲解链接 说明
一维
70 Climbing Stairs 视频讲解 Done
62 Unique Paths 视频讲解 Done
63 Unique Paths II 视频讲解 Done
120 Triangle 视频讲解 很少考
279 Perfect Squares 视频讲解 Done(Essentially an mathmatic problem)
139 Word Break 视频讲解 Done
375 Guess Number Higher or Lower II 视频讲解 hard to understand
312 Burst Balloons 视频讲解
322 Coin Change 视频讲解
二维
256 Paint House 视频讲解 Done
265 Paint House II 视频讲解 Done(half)
64 Minimum Path Sum 视频讲解 Done
72 Edit Distance 视频讲解
97 Interleaving String 视频讲解
174 Dungeon Game 视频讲解
221 Maximal Square 视频讲解
85 Maximal Rectangle 视频讲解
363 Max Sum of Rectangle No Larger Than K 视频讲解 TreeSet
化简
198 House Robber 视频讲解
213 House Robber II 视频讲解
276 Paint Fence 视频讲解
91 Decode Ways 视频讲解
10 Regular Expression Matching 视频讲解
44 Wildcard Matching 视频讲解

279

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.

explanation and my thought

Well, it is straightforward to come up with the dp formula:

In other words, we just define the same problem with an smaller input m as the subproblem, and calculate the optimal solution by reuse the result of subproblem. And it would take $O(N^2)$ to terminate since in each subproblem we need to traverse $O(N)$ subproblem to get the answer and there is totally $N$ subproblem.

The fastest solution in the discussion board is basically a mathematic one. It is pretty but could not be called as very useful one when you are in an interview. Just think about how embarrassing it would be when you gave that genius solution and your interviewer ask you about some details of this algorithm. What you want to say? Show them the paper and proof? LOL.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
map<int,int>dp;
class Solution {
public:
    int numSquares(int n) {
        if(dp.find(n)!=dp.end())return dp[n];
        if(n==0)return 0;
        if(n==1)return 1;
        int rootFloor=int(sqrt(n));
        int res=INT_MAX;
        for(int i=rootFloor;i>=1;i--){
            res=min(res,numSquares(n-i*i)+1);
        }
        dp[n]=res;
        return res;
       
    }
};

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.

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

Explanation and my thought

First Let’s talk about how could you find that it is a dynamic programming problem:

Firstly, greedy is not suitable there since there could be multiple choice to split the string and the result varies by each split:

in the example:

s=leetcode, wordDict=["lee","leet",""code"], if you do things greedily, you might choose the “lee” as the first word to split the s then you get stuck there since there is no word like tcode in the wordDict.

So the dynamic programming method here, and firstly let’s define the subproblem, there are two choices here, the first is to define the subproblem dp[i] so that the dp[i] is the answer for a substring start at index 0 and ends at index i, and the second solution is to define the subproblem as dp[i] [j] for the subproblem with substring start at i and ends at j.

If we observe the example, we could find that every valid string could be split like dp[j]+aWordInWordDict(j is some index >0 and <n). It could be proved using contradiction, so an one dimention array is enough to solve this problem, and the dp recurrence formula is like that:

Code

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(s.size()==0)return false;
        map<string,bool>M;
        for(string word:wordDict){
            M[word]=true;
        }
        vector<int>positions;
        positions.push_back(0);
        vector<bool>dp(s.size(),false);
        for(int i=0;i<s.size();i++){
            for(int pre:positions){
                if(M.find(s.substr(pre,i-pre+1))!=M.end()){
                    dp[i]=true;
                }
            }
            if(dp[i])positions.push_back(i+1);
        }
        return dp[dp.size()-1];
    }
};