DP慢慢总结
DP类型题总结
Longest Increasing Subsequence https://leetcode.com/problems/longest-increasing-subsequence/
Longest Common Subsequence
Longest Commen Substring
Longest Bitonic Subsequence: https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/
Maximum weight transformation of a given string: https://www.geeksforgeeks.org/maximum-weight-transformation-of-a-given-string/
House Robber类型题：选择偷还是不偷这家。
House Robber:
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
46
47
48
49
50
51
52
53/*
198. House Robber
Easy
3160
103
Favorite
Share
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.
Example 1:
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.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
*/
class Solution {
/*
rob(x) calculate the maximum value we can rob at position n.
1. rob(n) = rob(n-1)
2. rob(n) = rob(n-2) + nums[n]
return max(case1, case2)
recursive and have mant sub-problems.
*/
public int rob(int[] nums) {
if(nums.length==0)
return 0;
int len = nums.length;
int[] dp = new int[len+1];
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2;i<=dp.length-1;i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
}
return dp[len];
}
}House Robber II: 与上一道题不同的地方输入是一个环，我们可以考虑第一家偷或者不偷的情况。
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
46
47
48
49
50/*
213. House Robber II
Medium
1114
39
Favorite
Share
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:
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:
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.
*/
class Solution {
public int rob(int[] nums) {
if(nums==null || nums.length==0)
return 0;
if(nums.length==1){
return nums[0];
}
int len = nums.length;
return Math.max(robWithIndex(nums, 0, len-2), robWithIndex(nums, 1, len-1));
}
public int robWithIndex(int[] nums, int start, int end){
int[] dp = new int[end-start+1+1];
dp[0] = 0;
dp[1] = nums[start];
for(int i = 2;i<=dp.length-1;i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i+start-1]);
}
return dp[dp.length-1];
}
}House Robber III: https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/*
337. House Robber III
Medium
1845
38
Favorite
Share
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
Map<TreeNode, Integer> map = new HashMap<>();
return rob(root, map);
}
private int rob(TreeNode node, Map<TreeNode, Integer> map){
if(node==null)
return 0;
if(map.containsKey(node)){
return map.get(node);
}
int notRobRoot = rob(node.left, map) + rob(node.right, map);
int robRoot = node.val;
if(node.left!=null){
robRoot = robRoot + rob(node.left.left, map) + rob(node.left.right, map);
}
if(node.right!=null){
robRoot = robRoot + rob(node.right.left, map) + rob(node.right.right, map);
}
int ans = Math.max(notRobRoot, robRoot);
map.put(node, ans);
return ans;
}
}
Word Break类型题
Word Break： isWord(n) = isWord(i) && (s.substring(i) in HashSet), for i belongs to [0, n)
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
46
47
48
49
50
51
52
53/*
139. Word Break
Medium
2838
155
Favorite
Share
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:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
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:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
*/
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for(int i = 0;i<=n-1;i++){
for(int j = 0;j<=i;j++){
if(set.contains(s.substring(j, i+1)) && dp[j-1+1]){
dp[i+1] = true;
break;
}
}
}
return dp[n];
}
}Word Break II:这道题用List
[]储存结果会造成TLE，所以使用HashMap存储结果，也就是使用Top-down DFS+Memorization 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/*
140. Word Break II
Hard
1248
282
Favorite
Share
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:
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
Example 2:
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:
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
*/
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Map<String, List<String>> map = new HashMap<>();
Set<String> set= new HashSet<>(wordDict);
return dfs(s, map, set);
}
private List<String> dfs(String s, Map<String, List<String>> map, Set<String> set){
if(map.containsKey(s)){
return map.get(s);
}
List<String> ans = new LinkedList<>();
if(s.length()==0){
ans.add("");
return ans;
}
for(int i = 0 ;i<=s.length()-1;i++){
String s1 = s.substring(0, i);
String s2 = s.substring(i);
if(set.contains(s2)){
List<String> l = dfs(s1, map, set);
for(String ss:l){
if(ss.length()==0){
ans.add(s2);
}
else {
ans.add(ss+" "+s2);
}
}
}
else {
continue;
}
}
map.put(s, ans);
return ans;
}
}Concatenated Words：与Word Break I相似，拆分成对于每一个List中的String，去看所有长度小于它的Word能否构成这个String，能的话加入结果。所以这道题我们先排序，然后所有排在该String前面的词放入HashSet中，也就变成了Word Break I。
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/*
472. Concatenated Words
Hard
360
73
Favorite
Share
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example:
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Note:
The number of elements of the given array will not exceed 10,000
The length sum of elements in the given array will not exceed 600,000.
All the input string will only include lower case letters.
The returned elements order does not matter.
*/
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> ans = new LinkedList<>();
if(words == null || words.length<=1){
return ans;
}
Arrays.sort(words, (a, b)->{
return a.length()-b.length();
});
Set<String> set = new HashSet<>();
set.add(words[0]);
for(int i =1;i<=words.length-1;i++){
if(dfs(words[i], set)){
ans.add(words[i]);
}
set.add(words[i]);
}
return ans;
}
private boolean dfs(String word, Set<String> set){//this part is the same as 139
int n = word.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for(int i = 0;i<=n-1;i++){
for(int j = 0;j<=i;j++){
if(set.contains(word.substring(j, i+1)) && dp[j-1+1]){
dp[i+1] = true;
break;
}
}
}
return dp[n];
}
}