Skip to content

Commit 6ec35f3

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions with tag dp.
1 parent a82587f commit 6ec35f3

6 files changed

+284
-24
lines changed

‎README.md

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -579,6 +579,21 @@
579579
* [740. Delete and Earn](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/740.%20Delete%20and%20Earn.md)
580580
* [790. Domino and Tromino Tiling](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/790.%20Domino%20and%20Tromino%20Tiling.md)
581581
* [801. Minimum Swaps To Make Sequences Increasing](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/801.%20Minimum%20Swaps%20To%20Make%20Sequences%20Increasing.md)
582+
* [139. Word Break](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/139.%20Word%20Break.md)
583+
* [140. Word Break II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/140.%20Word%20Break%20II.md)
584+
* [818. Race Car](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/818.%20Race%20Car.md)
585+
* [300. Longest Increasing Subsequence](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/300.%20Longest%20Increasing%20Subsequence.md)
586+
* [673. Number of Longest Increasing Subsequence](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/673.%20Number%20of%20Longest%20Increasing%20Subsequence.md)
587+
* [72. Edit Distance](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/72.%20Edit%20Distance.md)
588+
* [10. Regular Expression Matching](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/10.%20Regular%20Expression%20Matching.md)
589+
* [44. Wildcard Matching](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/44.%20Wildcard%20Matching.md)
590+
* [97. Interleaving String](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/97.%20Interleaving%20String.md)
591+
* [115. Distinct Subsequences](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/115.%20Distinct%20Subsequences.md)
592+
* [583. Delete Operation for Two Strings](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/583.%20Delete%20Operation%20for%20Two%20Strings.md)
593+
* [712. Minimum ASCII Delete Sum for Two Strings](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/712.%20Minimum%20ASCII%20Delete%20Sum%20for%20Two%20Strings.md)
594+
* [322. Coin Change](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/322.%20Coin%20Change.md)
595+
* [377. Combination Sum IV](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/377.%20Combination%20Sum%20IV.md)
596+
582597

583598
## Algorithm(4th_Edition)
584599
Reading notes of book Algorithm(4th Algorithm),ISBN: 9787115293800.

‎leetcode/115. Distinct Subsequences.md

Lines changed: 34 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -70,7 +70,7 @@ class Solution {
7070
}
7171
```
7272

73-
* 延伸：s,t两个字符串，能否从s中移除一些字符变成b。
73+
* 延伸：s,t两个字符串，能否从s中移除一些字符变成t。
7474
```Java
7575
public static boolean stringChange(String s, String t){
7676
int sLen = s.length();
@@ -119,4 +119,36 @@ class Solution {
119119
return dp[sLen][tLen];
120120
}
121121
}
122-
```
122+
```
123+
124+
### Third Time
125+
* Method 1: dp[i][j]: this dp matrix saves the ways of reaching i index of target with j index of source string.
126+
![Imgur](https://i.imgur.com/wTJyS1Q.png)
127+
* Initialization: dp[0][0] = 1, nothing changed, 1 way.
128+
* dp[0][1: sLen] = 1: we need to delete all characters so there is only one way.
129+
* dp[i][i] = dp[i][j - 1]: Remove current character to get i + (if same character for target and source) dp[i - 1][j - 1]
130+
```Java
131+
class Solution {
132+
public int numDistinct(String s, String t) {
133+
char[] sArr = s.toCharArray(), tArr = t.toCharArray();
134+
int sLen = sArr.length, tLen = tArr.length;
135+
int[][] dp = new int[tLen + 1][sLen + 1];
136+
dp[0][0] = 1;
137+
for(int i = 1; i <= sLen; i++)
138+
dp[0][i] = dp[0][i - 1];
139+
for(int i = 1; i <= tLen; i++){
140+
for(int j = 1; j <= sLen; j++){
141+
dp[i][j] = dp[i][j - 1];
142+
if(sArr[j - 1] == tArr[i - 1]){
143+
dp[i][j] += dp[i - 1][j - 1];
144+
}
145+
}
146+
}
147+
return dp[tLen][sLen];
148+
}
149+
}
150+
```
151+
152+
### Reference
153+
1. [花花酱 LeetCode 115. Distinct Subsequences](http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-115-distinct-subsequences/)
154+

‎leetcode/322. Coin Change.md

Lines changed: 45 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -18,30 +18,53 @@ Output: -1
1818

1919
### Thinking:
2020
* Method 1:DP
21-
22-
```Java
23-
class Solution {
24-
public int coinChange(int[] coins, int amount) {
25-
int[] dp = new int[amount + 1];
26-
for(int i = 1; i < amount + 1; i++)
27-
dp[i] = -1;
28-
for(int c : coins)
29-
if(c < amount + 1)
30-
dp[c] = 1;
31-
for(int i = 1; i <= amount; i++){
32-
if(dp[i] != -1) continue;
33-
saveMin(dp, coins, i);
21+
```Java
22+
class Solution {
23+
public int coinChange(int[] coins, int amount) {
24+
int[] dp = new int[amount + 1];
25+
for(int i = 1; i < amount + 1; i++)
26+
dp[i] = -1;
27+
for(int c : coins)
28+
if(c < amount + 1)
29+
dp[c] = 1;
30+
for(int i = 1; i <= amount; i++){
31+
if(dp[i] != -1) continue;
32+
saveMin(dp, coins, i);
33+
}
34+
return dp[amount];
35+
}
36+
private void saveMin(int[] dp, int[] coins, int index){
37+
int min = Integer.MAX_VALUE;
38+
for(int c : coins){
39+
if(index - c >= 0 && dp[index - c] != -1){
40+
min = Math.min(min, dp[index - c]);
41+
}
42+
}
43+
dp[index] = min == Integer.MAX_VALUE ? -1 : min + 1;
3444
}
35-
return dp[amount];
3645
}
37-
private void saveMin(int[] dp, int[] coins, int index){
38-
int min = Integer.MAX_VALUE;
39-
for(int c : coins){
40-
if(index - c >= 0 && dp[index - c] != -1){
41-
min = Math.min(min, dp[index - c]);
46+
```
47+
48+
### Second Time
49+
* Method 1: dp AC 83.88%
50+
```Java
51+
class Solution {
52+
public int coinChange(int[] coins, int amount) {
53+
int len = coins.length;
54+
int[] dp = new int[amount + 1];
55+
Arrays.fill(dp, Integer.MAX_VALUE >> 1);
56+
dp[0] = 0;
57+
for(int coin : coins){
58+
if(coin <= amount)
59+
dp[coin] = 1;
60+
}
61+
for(int i = 1; i <= amount; i++){
62+
if(dp[i] == 1) continue;
63+
for(int coin : coins){
64+
dp[i] = Math.min(i - coin >= 0 ? dp[i - coin] + 1: Integer.MAX_VALUE >> 1, dp[i]);
65+
}
4266
}
67+
return dp[amount] == Integer.MAX_VALUE >> 1 ? -1: dp[amount];
4368
}
44-
dp[index] = min == Integer.MAX_VALUE ? -1 : min + 1;
4569
}
46-
}
47-
```
70+
```

‎leetcode/377. Combination Sum IV.md

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
## 377. Combination Sum IV
2+
3+
### Question
4+
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
5+
6+
```
7+
Example:
8+
9+
nums = [1, 2, 3]
10+
target = 4
11+
12+
The possible combination ways are:
13+
(1, 1, 1, 1)
14+
(1, 1, 2)
15+
(1, 2, 1)
16+
(1, 3)
17+
(2, 1, 1)
18+
(2, 2)
19+
(3, 1)
20+
21+
Note that different sequences are counted as different combinations.
22+
23+
Therefore the output is 7.
24+
```
25+
26+
Follow up:
27+
* What if negative numbers are allowed in the given array?
28+
* How does it change the problem?
29+
* What limitation we need to add to the question to allow negative numbers?
30+
31+
### Solution:
32+
* Method 1: Search dfs TLE
33+
```Java
34+
class Solution {
35+
private int res = 0;
36+
public int combinationSum4(int[] nums, int target) {
37+
dfs(nums, target, 0);
38+
return res;
39+
}
40+
private void dfs(int[] nums, int target, int temp){
41+
if(temp == target) res++;
42+
else if(temp < target){
43+
for(int i = 0; i < nums.length; i++){
44+
dfs(nums, target, temp + nums[i]);
45+
}
46+
}
47+
}
48+
}
49+
```
50+
51+
* Method 1:DP AC 87.93%
52+
```Java
53+
class Solution {
54+
public int combinationSum4(int[] nums, int target) {
55+
int[] dp = new int[target + 1];
56+
dp[0] = 1;
57+
for(int i = 1; i <= target; i++){
58+
for(int num : nums){
59+
dp[i] += i - num >= 0 ? dp[i - num]: 0;
60+
}
61+
}
62+
return dp[target];
63+
}
64+
}
65+
```

‎leetcode/583. Delete Operation for Two Strings.md

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
## 583. Delete Operation for Two Strings
2+
3+
### Question
4+
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
5+
6+
```
7+
Example 1:
8+
9+
Input: "sea", "eat"
10+
Output: 2
11+
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
12+
```
13+
14+
Note:
15+
* The length of given words won't exceed 500.
16+
* Characters in given words can only be lower-case letters.
17+
18+
19+
### Solution:
20+
* Method 1: dp[i][j]: the minimum step for have same string for s[0:i] and t[0: j] AC 70.05%
21+
* Initialization: dp[0][0] = 0. Nothing need to do.
22+
* dp[0][i] = i, dp[i][0] = i. Remove all characters from a string to reach a empty one.
23+
* State transfer function:
24+
* if characters are the same: dp[i][j] = dp[i - 1][j - 1]
25+
* if not the same:
26+
* remove both of current characters: dp[i - 1][j - 1] + 2
27+
* remove one character from either string: dp[i - 1][j] + 1 && dp[i][j - 1] + 1.
28+
* select the minimum from the three methods.
29+
```Java
30+
class Solution {
31+
public int minDistance(String word1, String word2) {
32+
char[] arr1 = word1.toCharArray(), arr2 = word2.toCharArray();
33+
int len1 = arr1.length, len2 = arr2.length;
34+
int[][] dp = new int[len1 + 1][len2 + 1];
35+
dp[0][0] = 0;
36+
for(int i = 1; i <= len1; i++)
37+
dp[i][0] = i;
38+
for(int i = 1; i <= len2; i++)
39+
dp[0][i] = i;
40+
for(int i = 1; i <= len1; i++){
41+
for(int j = 1; j <= len2; j++){
42+
if(arr1[i - 1] == arr2[j - 1])
43+
dp[i][j] = dp[i - 1][j - 1];
44+
else{
45+
dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
46+
Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
47+
}
48+
}
49+
}
50+
return dp[len1][len2];
51+
}
52+
}
53+
```
54+
55+
56+

‎leetcode/712. Minimum ASCII Delete Sum for Two Strings.md

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
## 712. Minimum ASCII Delete Sum for Two Strings
2+
3+
### Question
4+
Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.
5+
6+
```
7+
Example 1:
8+
9+
Input: s1 = "sea", s2 = "eat"
10+
Output: 231
11+
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
12+
Deleting "t" from "eat" adds 116 to the sum.
13+
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
14+
15+
Example 2:
16+
17+
Input: s1 = "delete", s2 = "leet"
18+
Output: 403
19+
Explanation: Deleting "dee" from "delete" to turn the string into "let",
20+
adds 100[d]+101[e]+101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum.
21+
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
22+
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
23+
```
24+
25+
Note:
26+
* 0 < s1.length, s2.length <= 1000.
27+
* All elements of each string will have an ASCII value in [97, 122].
28+
29+
### Solution:
30+
* Method 1: dp[i][j]: the minimum asc ii for have same string for s[0:i] and t[0: j] AC 97%
31+
* Initialization: dp[0][0] = 0. Nothing need to delete.
32+
* dp[0][i] = char at s2, dp[i][0] = char at s1. Remove all characters from a string to reach a empty one.
33+
* State transfer function:
34+
* if characters are the same: dp[i][j] = dp[i - 1][j - 1]
35+
* if not the same:
36+
* remove both of current characters: dp[i - 1][j - 1] + s1[i - 1] + s2[j - 1]
37+
* remove one character from either string: dp[i - 1][j] + s1[i - 1] && dp[i][j - 1] + s2[j - 1].
38+
* select the minimum from the three methods.
39+
```Java
40+
class Solution {
41+
public int minDistance(String word1, String word2) {
42+
char[] arr1 = word1.toCharArray(), arr2 = word2.toCharArray();
43+
int len1 = arr1.length, len2 = arr2.length;
44+
int[][] dp = new int[len1 + 1][len2 + 1];
45+
dp[0][0] = 0;
46+
for(int i = 1; i <= len1; i++)
47+
dp[i][0] = i;
48+
for(int i = 1; i <= len2; i++)
49+
dp[0][i] = i;
50+
for(int i = 1; i <= len1; i++){
51+
for(int j = 1; j <= len2; j++){
52+
if(arr1[i - 1] == arr2[j - 1])
53+
dp[i][j] = dp[i - 1][j - 1];
54+
else{
55+
dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
56+
Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
57+
}
58+
}
59+
}
60+
return dp[len1][len2];
61+
}
62+
}
63+
```
64+
65+
### Related Question
66+
1. [583. Delete Operation for Two Strings](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/583.%20Delete%20Operation%20for%20Two%20Strings.md)
67+
68+
69+

0 commit comments

Comments
 (0)