Moved the derive formula after initialize dp.

gazeldx · gazeldx · commit 9ef7bb9cea3b · 2024-11-26T13:59:02.000+08:00
diff --git a/0053-maximum-subarray.md b/0053-maximum-subarray.md
@@ -28,10 +28,16 @@ These five steps are a pattern for solving dynamic programming problems.
     * 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.
     * Imagine that `dp[i]` represents the `largest sum` at index `i`. The `dp[i + 1]` cannot be calculated by `dp[i]`. So we have to change this meaning.
     * Then consider that `dp[i]` represents the `current sum` at index `i`. We can see the `largest sum` is recorded in the `current sum` array. It may work.
-2. Determine the `dp` array's recurrence formula
-    * `dp[i] = max(nums[i], dp[i - 1] + nums[i])`.
-3. Determine the `dp` array's initial value
+2. Determine the `dp` array's initial value
     * `dp[i] = nums[i]` would be good.
+3. Determine the `dp` array's recurrence formula
+    * Use an example:
+```
+nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
+dp   = [-2, 1, -2, 4,  3, 5, 6,  1, 5]
+```
+   * After analyzing the sample `dp` data, we can derive the `recurrence formula`:
+    * `dp[i] = max(nums[i], dp[i - 1] + nums[i])`.
 4. Determine the `dp` array's traversal order
     * `dp[i]` depends on `dp[i - 1]`, so we should traverse the `dp` array from left to right.
 5. Check the `dp` array's value
@@ -41,6 +47,22 @@ These five steps are a pattern for solving dynamic programming problems.
 * Time: `O(n)`.
 * Space: `O(n)`.
 
+## Java
+
+```java
+class Solution {
+    int[] dp = nums.clone();
+    int result = dp[0];
+
+    for (int i = 1; i < dp.length; i++) {
+        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
+        if (dp[i] > result) result = dp[i];
+    }
+
+    return result; // or 'return Arrays.stream(dp).max().getAsInt();'
+}
+```
+
 ## Python
 ```python
 class Solution:
@@ -69,22 +91,6 @@ public:
 };
 ```
 
-## Java
-
-```java
-class Solution {
-    int[] dp = nums.clone();
-    int result = dp[0];
-
-    for (int i = 1; i < dp.length; i++) {
-        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
-        if (dp[i] > result) result = dp[i];
-    }
-
-    return result; // or 'return Arrays.stream(dp).max().getAsInt();'
-}
-```
-
 ## C#
 ```c#
 public class Solution {
diff --git a/0392-is-subsequence.md b/0392-is-subsequence.md
@@ -28,27 +28,36 @@ These five steps are a pattern for solving dynamic programming problems.
     * 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.
     * `dp[i][j]` represents whether the first `i` letters of `s` are a subsequence of `t`'s first `j` letters.
     * The value of `dp[i][j]` is `true` or `false`.
-2. Determine the `dp` array's recurrence formula
+2. Determine the `dp` array's initial value
    * Use an example:
 ```
+After initialized, the 'dp' array would be:
+s = "abc", t = "ahbgdc"
+#     a h b g d c
+#   T T T T T T T # dp[0]
+# a F F F F F F F
+# b F F F F F F F
+# c F F F F F F F
+```
+   * `dp[0][j] = true` because `dp[0]` represents the empty string, and empty string is a subsequence of any string.
+   * `dp[i][j] = false (i != 0)`.
+3. Determine the `dp` array's recurrence formula
+```
+The final 'dp' array would be:
 s = "abc", t = "ahbgdc"
 #     a h b g d c
 #   T T T T T T T
 # a F T T T T T T
 # b F F F T T T T
 # c F F F F F F T
 ```
-   * Recurrence formula:
+   * After analyzing the sample `dp` data, we can derive the `recurrence formula`:
 ```
 if s[i - 1] == t[j - 1]
   dp[i][j] = dp[i - 1][j - 1]
 else
   dp[i][j] = dp[i][j - 1]
 ```
-
-3. Determine the `dp` array's initial value
-    * `dp[0][j] = true` because `dp[0]` represents the empty string and empty string is a subsequence of any string.
-    * `dp[i][j] = false (i != 0)`.
 4. Determine the `dp` array's traversal order
     * `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.
 5. Check the `dp` array's value
diff --git a/0583-delete-operation-for-two-strings.md b/0583-delete-operation-for-two-strings.md
@@ -28,17 +28,19 @@ These five steps are a pattern for solving dynamic programming problems.
     * 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.
     * `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.
     * The value of `dp[i][j]` is an integer.
-2. Determine the `dp` array's recurrence formula
-   * Use an example:
+2. Determine the `dp` array's initial value
+    * Use an example:
 ```
 After initialized, the 'dp' array would be:  
 #     e a t
-#   0 1 2 3 # dp[0] is for empty string, the number of steps is just the number of chars to be deleted
+#   0 1 2 3 # dp[0]
 # s 1 0 0 0
 # e 2 0 0 0
 # a 3 0 0 0
 ```
-
+   * `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
+   * `dp[i][0] = i`, the reason is the same as previous line, yet in vertical direction.
+3. Determine the `dp` array's recurrence formula
 ```
 The final 'dp' array would be:
 #     e a t
@@ -47,17 +49,13 @@ The final 'dp' array would be:
 # e 2 1 2 3
 # a 3 2 1 2
 ```
-   * Recurrence formula:
+   * After analyzing the sample `dp` data, we can derive the `recurrence formula`:
 ```python
 if word1[i - 1] == word2[j - 1]
     dp[i][j] = dp[i - 1][j - 1]
 else
     dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
 ```
-
-3. Determine the `dp` array's initial value
-    * `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
-    * `dp[i][0] = i`, the reason is the same as previous line, yet in vertical direction. 
 4. Determine the `dp` array's traversal order
     * `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.
 5. Check the `dp` array's value
diff --git a/README.md b/README.md
@@ -1,3 +1,6 @@
 # A best practice for the LeetCode problems
 - [53. Maximum Subarray](./0053-maximum-subarray.md)
 - [392. Is Subsequence](./0392-is-subsequence.md)
+- [583. Delete Operation for Two Strings](./0583-delete-operation-for-two-strings.md)
+
+- More LeetCode problems will be added soon...
