Skip to content

Commit 87a8e48

Browse files
gazeldxgazeldx
committed
Update all solutions' changes in 2025-04-06.
1 parent 73114f8 commit 87a8e48

18 files changed

+240
-343
lines changed

‎en/1-1000/392-is-subsequence.md

+38-51
Original file line numberDiff line numberDiff line change
@@ -230,15 +230,16 @@ end
230230

231231
## Intuition 2
232232

233-
- Solution 1 is essentially a "dynamic programming" algorithm implemented with rolling variables. It is easy to understand, and the space complexity is reduced to `O(1)`.
233+
- `Solution 1` is essentially a "dynamic programming" algorithm implemented with `rolling variables`. It is easy to understand, and the space complexity is reduced to `O(1)`.
234234
- But now, not only do we not reduce the dimension, but we also increase the dimension. It will be more difficult to understand and implement. So why do this thankless task?
235235
<details><summary>Click to view the answer</summary><p> Because it can handle a more complex scenario (e.g. [583. Delete Operation for Two Strings](583-delete-operation-for-two-strings.md)) that is common in dynamic programming. </p></details>
236-
- In this question, can we use a one-dimensional rolling array to implement the "dynamic programming" algorithm?
237-
<details><summary>Click to view the answer</summary><p> Of course, but considering that a one-dimensional rolling array is not as easy to understand as a two-dimensional array, and the implementation process is also prone to errors, so here I didn't give the relevant code implementation. If you are interested, you can try it. </p></details>
236+
- In this question, can we use a `one-dimensional rolling array` to implement the "dynamic programming" algorithm?
237+
<details><summary>Click to view the answer</summary><p> Of course, but considering that for this problem a `one-dimensional rolling array` is not as easy to understand as a `two-dimensional array`, and the implementation process is also prone to errors, so here I didn't give the relevant code implementation. If you are interested, you can try it. </p></details>
238+
- The **compare two strings** question is about dealing with "two swappable arrays". After doing similar questions many times, we will form the intuition of using `two-dimensional arrays` for dynamic programming.
238239

239240
## Pattern of "Dynamic Programming"
240241

241-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
242+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
242243

243244
#### "Dynamic programming" is divided into five steps
244245

@@ -275,18 +276,10 @@ After reading the above, do you feel that "dynamic programming" is not that diff
275276

276277
## Steps
277278

278-
It is a question of **comparing two strings**. After doing similar questions many times, we will develop an intuition to use `dynamic programming` with two-dimensional arrays.
279-
280-
### Common steps in dynamic programming
281-
282-
These five steps are a pattern for solving `dynamic programming` problems.
283-
284-
1. Determine the **meaning** of the `dp[i][j]`
285-
- Since there are two strings, we can use two-dimensional arrays as the default option.
286-
- At first, try to use the problem's `return` value as the value of `dp[i][j]` to determine the meaning of `dp[i][j]`. If it doesn't work, try another way.
279+
1. Determine the **meaning** of the `dp[i][j]`.
287280
- `dp[i][j]` represents whether the first `i` letters of `s` are a subsequence of `t`'s first `j` letters.
288281
- `dp[i][j]` is `true` or `false`.
289-
2. Determine the `dp` array's initial value
282+
2. Determine the `dp` array's initial value.
290283
- Use an example:
291284

292285
```
@@ -300,45 +293,39 @@ These five steps are a pattern for solving `dynamic programming` problems.
300293
```
301294
- `dp[0][j] = true` because `dp[0]` represents the empty string, and empty string is a subsequence of any string.
302295
- `dp[i][j] = false (i != 0)`.
303-
3. Determine the `dp` array's recurrence formula
304-
- Try to complete the `dp` grid. In the process, you will get inspiration to derive the formula.
296+
3. Fill in the `dp` grid data "in order" according to an example.
305297
306-
```
307-
1. s = "a", t = "ahbgdc"
308-
# a h b g d c
309-
# T T T T T T T
310-
# a F T T T T T T # dp[1]
311-
```
312-
```
313-
2. s = "ab", t = "ahbgdc"
314-
# a h b g d c
315-
# T T T T T T T
316-
# a F T T T T T T
317-
# b F F F T T T T
318-
```
319-
```
320-
3. s = "abc", t = "ahbgdc"
321-
# a h b g d c
322-
# T T T T T T T
323-
# a F T T T T T T
324-
# b F F F T T T T
325-
# c F F F F F F T # dp[3]
326-
```
327-
- When analyzing the sample `dp` grid, remember there are three important points which you should pay special attention to: `dp[i - 1][j - 1]`, `dp[i - 1][j]` and `dp[i][j - 1]`. The current `dp[i][j]` often depends on them.
328-
- If the question is also true in reverse (swap `s` and `t`), and we need to use `dp[i - 1][j]` or `dp[i][j - 1]`, then we probably need to use both of them.
329-
- We can derive the `Recurrence Formula`:
298+
```
299+
1. s = "a", t = "ahbgdc"
300+
# a h b g d c
301+
# T T T T T T T
302+
# a F T T T T T T # dp[1]
303+
```
304+
```
305+
2. s = "ab", t = "ahbgdc"
306+
# a h b g d c
307+
# T T T T T T T
308+
# a F T T T T T T
309+
# b F F F T T T T
310+
```
311+
```
312+
3. s = "abc", t = "ahbgdc"
313+
# a h b g d c
314+
# T T T T T T T
315+
# a F T T T T T T
316+
# b F F F T T T T
317+
# c F F F F F F T # dp[3]
318+
```
319+
4. Based on the `dp` grid data, derive the "recursive formula".
330320
331-
```ruby
332-
if s[i - 1] == t[j - 1]
333-
dp[i][j] = dp[i - 1][j - 1]
334-
else
335-
dp[i][j] = dp[i][j - 1]
336-
end
337-
```
338-
4. Determine the `dp` array's traversal order
339-
- `dp[i][j]` depends on `dp[i - 1][j - 1]` and `dp[i][j - 1]`, so we should traverse the `dp` array from top to bottom, then from left to right.
340-
5. Check the `dp` array's value
341-
- Print the `dp` to see if it is as expected.
321+
```ruby
322+
if s[i - 1] == t[j - 1]
323+
dp[i][j] = dp[i - 1][j - 1]
324+
else
325+
dp[i][j] = dp[i][j - 1]
326+
end
327+
```
328+
5. Write a program and print the `dp` array. If it is not as expected, adjust it.
342329
343330
## Complexity
344331

‎en/1-1000/416-partition-equal-subset-sum.md

+2-2
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@ Given an integer array `nums`, return `true` if you can partition the array into
4242

4343
## Pattern of "Dynamic Programming"
4444

45-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
45+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
4646

4747
#### "Dynamic programming" is divided into five steps
4848

@@ -371,7 +371,7 @@ During the interview, you need to remember it. Is there any way to not worry abo
371371

372372
## Pattern of "Dynamic Programming"
373373

374-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
374+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
375375

376376
#### "Dynamic programming" is divided into five steps
377377

‎en/1-1000/474-ones-and-zeroes.md

+1-1
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ This question is difficult. It is recommended to complete a simple question of t
5353

5454
## Pattern of "Dynamic Programming"
5555

56-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
56+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
5757

5858
#### "Dynamic programming" is divided into five steps
5959

‎en/1-1000/494-target-sum.md

+1-1
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ This problem is quite difficult if you have not solved similar problems before.
4848

4949
## Pattern of "Dynamic Programming"
5050

51-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
51+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
5252

5353
#### "Dynamic programming" is divided into five steps
5454

‎en/1-1000/5-longest-palindromic-substring.md

+1-1
Original file line numberDiff line numberDiff line change
@@ -60,7 +60,7 @@ If we use brute-force and check whether for every start and end position a subst
6060

6161
## Pattern of "Dynamic Programming"
6262

63-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
63+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
6464

6565
#### "Dynamic programming" is divided into five steps
6666

‎en/1-1000/53-maximum-subarray.md

+28-42
Original file line numberDiff line numberDiff line change
@@ -45,18 +45,15 @@ Given an integer array `nums`, find the `subarray` with the largest sum, and ret
4545

4646
## Intuition 1
4747

48-
- This problem can be solved by using `Greedy Algorithm` (please see `solution 2`), but here we will use another way.
49-
- Imagine the size of nums is `i`, let us consider if the same question is applied to the `subarray` of `nums` from index `0` to `i - 1`.
50-
- The answer is `yes`. Then let us think if the `i - 1`'s answer could impact the answer of `i`.
51-
- The answer is still `yes`. What would be the impact?
52-
- For `nums[i]`,
48+
- This problem can be solved by using `Greedy Algorithm` (please see `solution 2`), yet here we will use another way.
49+
- For `nums[i]`:
5350
1. If the `previous sum` is negative, we can discard `previous sum`;
5451
2. If the `previous sum` is positive, we can add `previous sum` to the `current sum`.
55-
- So we can use `Dynamic Programming` to solve the problem. The characteristic of the "Dynamic Programming" algorithm is that the value of `dp[i]` is converted from `dp[i - 1]`.
52+
- Therefore, it meets the characteristics of a `dynamic programming` problem.
5653

5754
## Pattern of "Dynamic Programming"
5855

59-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
56+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
6057

6158
#### "Dynamic programming" is divided into five steps
6259

@@ -93,47 +90,36 @@ After reading the above, do you feel that "dynamic programming" is not that diff
9390

9491
## Steps
9592

96-
### Common steps in dynamic programming
97-
98-
These five steps are a pattern for solving `dynamic programming` problems.
99-
10093
1. Determine the **meaning** of the `dp[i]`
101-
- At first, try to use the problem's `return` value as the value of `dp[i]` to determine the meaning of `dp[i]`. If it doesn't work, try another way.
10294
- Imagine that `dp[i]` represents the `largest sum` at index `i`. Is this okay?
10395
mark-detail `dp[i + 1]` cannot be calculated by `dp[i]`. So we have to change the meaning. mark-detail
10496
- How to design it?
10597
mark-detail If `dp[i]` represents the `current sum` at index `i`, `dp[i + 1]` can be calculated by `dp[i]`. Finally, we can see that the `maximum sum` is recorded in the `current sum` array. mark-detail
10698
2. Determine the `dp` array's initial value
107-
- Use an example:
108-
109-
```ruby
110-
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
111-
dp = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
112-
```
113-
- `dp[i] = nums[i]` would be good.
114-
3. Determine the `dp` array's recurrence formula
115-
- Try to complete the `dp` array. In the process, you will get inspiration to derive the formula.
116-
117-
```ruby
118-
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
119-
dp = [-2, 1, N, N, N, N, N, N, N] # N means don't pay attention to it now
120-
dp = [-2, 1, -2, N, N, N, N, N, N]
121-
dp = [-2, 1, -2, 4, N, N, N, N, N]
122-
dp = [-2, 1, -2, 4, 3, N, N, N, N]
123-
dp = [-2, 1, -2, 4, 3, 5, N, N, N]
124-
dp = [-2, 1, -2, 4, 3, 5, 6, N, N]
125-
dp = [-2, 1, -2, 4, 3, 5, 6, 1, N]
126-
dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
127-
```
128-
- After analyzing the sample `dp` array, we can derive the `Recurrence Formula`:
129-
130-
```python
131-
dp[i] = max(nums[i], dp[i - 1] + nums[i])
132-
```
133-
4. Determine the `dp` array's traversal order
134-
- `dp[i]` depends on `dp[i - 1]`, so we should traverse the `dp` array from left to right.
135-
5. Check the `dp` array's value
136-
- Print the `dp` to see if it is as expected.
99+
100+
```ruby
101+
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
102+
dp = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
103+
```
104+
3. Fill in the `dp` grid data "in order" according to an example.
105+
106+
```ruby
107+
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
108+
dp = [-2, 1, N, N, N, N, N, N, N] # N means don't pay attention to it now
109+
dp = [-2, 1, -2, N, N, N, N, N, N]
110+
dp = [-2, 1, -2, 4, N, N, N, N, N]
111+
dp = [-2, 1, -2, 4, 3, N, N, N, N]
112+
dp = [-2, 1, -2, 4, 3, 5, N, N, N]
113+
dp = [-2, 1, -2, 4, 3, 5, 6, N, N]
114+
dp = [-2, 1, -2, 4, 3, 5, 6, 1, N]
115+
dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
116+
```
117+
4. Based on the `dp` grid data, derive the "recursive formula".
118+
119+
```python
120+
dp[i] = max(nums[i], dp[i - 1] + nums[i])
121+
```
122+
5. Write a program and print the `dp` array. If it is not as expected, adjust it.
137123

138124
## Complexity
139125

‎en/1-1000/583-delete-operation-for-two-strings.md

+35-46
Original file line numberDiff line numberDiff line change
@@ -34,11 +34,12 @@ In one **step**, you can delete exactly one character in either string.
3434

3535
## Intuition
3636

37-
It is a question of **comparing two strings**. After doing similar questions many times, we will develop an intuition to use `dynamic programming with two-dimensional arrays`.
37+
It is a question of **comparing two strings** which is about dealing with "two swappable arrays".
38+
After doing similar questions many times, we will form the intuition of using `two-dimensional arrays` for dynamic programming.
3839

3940
## Pattern of "Dynamic Programming"
4041

41-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
42+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
4243

4344
#### "Dynamic programming" is divided into five steps
4445

@@ -75,16 +76,10 @@ After reading the above, do you feel that "dynamic programming" is not that diff
7576

7677
## Steps
7778

78-
### Common steps in dynamic programming
79-
80-
These five steps are a pattern for solving `dynamic programming` problems.
81-
82-
1. Determine the **meaning** of the `dp[i][j]`
83-
- Since there are two strings, we can use two-dimensional arrays as the default option.
84-
- At first, try to use the problem's `return` value as the value of `dp[i][j]` to determine the meaning of `dp[i][j]`. If it doesn't work, try another way.
79+
1. Determine the **meaning** of the `dp[i][j]`.
8580
- `dp[i][j]` represents the **minimum** number of steps required to make `word1`'s first `i` letters and `word2`'s first `j` letters the same.
8681
- `dp[i][j]` is an integer.
87-
2. Determine the `dp` array's initial value
82+
2. Determine the `dp` array's initial value.
8883
- Use an example:
8984

9085
```
@@ -97,44 +92,38 @@ These five steps are a pattern for solving `dynamic programming` problems.
9792
```
9893
- `dp[0][j] = j`, because `dp[0]` represents the empty string, and the number of steps is just the number of chars to be deleted.
9994
- `dp[i][0] = i`, the reason is the same as the previous line, just viewed in vertical direction.
100-
3. Determine the `dp` array's recurrence formula
101-
- Try to complete the grid. In the process, you will get inspiration to derive the formula.
95+
3. Fill in the `dp` grid data "in order" according to an example.
10296
103-
```
104-
1. word1 = "s", word2 = "eat"
105-
# e a t
106-
# 0 1 2 3
107-
# s 1 2 3 4 # dp[1]
108-
```
109-
```
110-
2. word1 = "se", word2 = "eat"
111-
# e a t
112-
# 0 1 2 3
113-
# s 1 2 3 4
114-
# e 2 1 2 3
115-
```
116-
```
117-
3. word1 = "sea", word2 = "eat"
118-
# e a t
119-
# 0 1 2 3
120-
# s 1 2 3 4
121-
# e 2 1 2 3
122-
# a 3 2 1 2
123-
```
124-
- When analyzing the sample `dp` grid, remember there are three important points which you should pay special attention to: `dp[i - 1][j - 1]`, `dp[i - 1][j]` and `dp[i][j - 1]`. The current `dp[i][j]` often depends on them.
125-
- If the question is also true in reverse (swap `word1` and `word2`), and we need to use `dp[i - 1][j]` or `dp[i][j - 1]`, then we probably need to use both of them.
126-
- We can derive the `Recurrence Formula`:
97+
```
98+
1. word1 = "s", word2 = "eat"
99+
# e a t
100+
# 0 1 2 3
101+
# s 1 2 3 4 # dp[1]
102+
```
103+
```
104+
2. word1 = "se", word2 = "eat"
105+
# e a t
106+
# 0 1 2 3
107+
# s 1 2 3 4
108+
# e 2 1 2 3
109+
```
110+
```
111+
3. word1 = "sea", word2 = "eat"
112+
# e a t
113+
# 0 1 2 3
114+
# s 1 2 3 4
115+
# e 2 1 2 3
116+
# a 3 2 1 2
117+
```
118+
4. Based on the `dp` grid data, derive the "recursive formula".
127119
128-
```python
129-
if word1[i - 1] == word2[j - 1]
130-
dp[i][j] = dp[i - 1][j - 1]
131-
else
132-
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
133-
```
134-
4. Determine the `dp` array's traversal order
135-
- `dp[i][j]` depends on `dp[i - 1][j - 1]`, `dp[i - 1][j]` and `dp[i][j - 1]`, so we should traverse the `dp` array from top to bottom, then from left to right.
136-
5. Check the `dp` array's value
137-
- Print the `dp` to see if it is as expected.
120+
```python
121+
if word1[i - 1] == word2[j - 1]
122+
dp[i][j] = dp[i - 1][j - 1]
123+
else
124+
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
125+
```
126+
5. Write a program and print the `dp` array. If it is not as expected, adjust it.
138127
139128
## Complexity
140129

‎en/1001-2000/1049-last-stone-weight-ii.md

+1-1
Original file line numberDiff line numberDiff line change
@@ -67,7 +67,7 @@ we can combine 1 and 1 to get 0, so the array converts to [1], then that&#39;s t
6767

6868
## Pattern of "Dynamic Programming"
6969

70-
`Dynamic programming` requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be derived from the value of the previous `dp[x][y]` related to it.
70+
"Dynamic Programming" requires the use of the `dp` array to store the results. The value of `dp[i][j]` can be converted from its previous (or multiple) values ​​through a formula. Therefore, the value of `dp[i][j]` is derived step by step, and it is related to the previous `dp` record value.
7171

7272
#### "Dynamic programming" is divided into five steps
7373

0 commit comments

Comments
 (0)