`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.

1. Determine the meaning of each value of the array `dp`.

2. Initialize the value of the array `dp`.

3. Fill in the `dp` grid data "in order" according to an example.

4. Based on the `dp` grid data, derive the "recursive formula".

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

1. Determine the meaning of each value of the array `dp`.

- First determine whether `dp` is a one-dimensional array or a two-dimensional array. A `one-dimensional rolling array` means that the values ​​of the array are overwritten at each iteration. Most of the time, using `one-dimensional rolling array` instead of `two-dimensional array` can simplify the code; but for some problems, such as operating "two swappable arrays", for the sake of ease of understanding, it is better to use `two-dimensional array`.

- Try to use the meaning of the `return value` required by the problem as the meaning of `dp[i]` (one-dimensional) or `dp[i][j]` (two-dimensional). It works about 60% of the time. If it doesn't work, try other meanings.

- Try to save more information in the design. Repeated information only needs to be saved once in a `dp[i]`.

- Use simplified meanings. If the problem can be solved with `boolean value`, don't use `numeric value`.

2. Initialize the value of the array `dp`. The value of `dp` involves two levels:

1. The length of `dp`. Usually: `condition array length plus 1` or `condition array length`.

2. The value of `dp[i]` or `dp[i][j]`. `dp[0]` or `dp[0][0]` sometimes requires special treatment.

3. Fill in the `dp` grid data "in order" according to an example.

- The "recursive formula" is the core of the "dynamic programming" algorithm. But the "recursive formula" is obscure. If you want to get it, you need to make a table and use data to inspire yourself.

- If the original example is not good enough, you need to redesign one yourself.

- According to the example, fill in the `dp` grid data "in order", which is very important because it determines the traversal order of the code.

- Most of the time, from left to right, from top to bottom. But sometimes it is necessary to traverse from right to left, from bottom to top, from the middle to the right (or left), such as the "palindrome" problems. Sometimes, it is necessary to traverse a line twice, first forward and then backward.

- When the order is determined correctly, the starting point is determined. Starting from the starting point, fill in the `dp` grid data "in order". This order is also the order in which the program processes.

- In this process, you will get inspiration to write a "recursive formula". If you can already derive the formula, you do not need to complete the grid.

4. Based on the `dp` grid data, derive the "recursive formula".

- There are three special positions to pay 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.

- When operating "two swappable arrays", due to symmetry, we may need to use `dp[i - 1][j]` and `dp[i][j - 1]` at the same time.

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

- Focus on analyzing those values that are not as expected.

After reading the above, do you feel that "dynamic programming" is not that difficult? Try to solve this problem. 🤗

`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.

1. Determine the meaning of each value of the array `dp`.

2. Initialize the value of the array `dp`.

3. Fill in the `dp` grid data "in order" according to an example.

4. Based on the `dp` grid data, derive the "recursive formula".

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

1. Determine the meaning of each value of the array `dp`.

- First determine whether `dp` is a one-dimensional array or a two-dimensional array. A `one-dimensional rolling array` means that the values ​​of the array are overwritten at each iteration. Most of the time, using `one-dimensional rolling array` instead of `two-dimensional array` can simplify the code; but for some problems, such as operating "two swappable arrays", for the sake of ease of understanding, it is better to use `two-dimensional array`.

- Try to use the meaning of the `return value` required by the problem as the meaning of `dp[i]` (one-dimensional) or `dp[i][j]` (two-dimensional). It works about 60% of the time. If it doesn't work, try other meanings.

- Try to save more information in the design. Repeated information only needs to be saved once in a `dp[i]`.

- Use simplified meanings. If the problem can be solved with `boolean value`, don't use `numeric value`.

2. Initialize the value of the array `dp`. The value of `dp` involves two levels:

1. The length of `dp`. Usually: `condition array length plus 1` or `condition array length`.

2. The value of `dp[i]` or `dp[i][j]`. `dp[0]` or `dp[0][0]` sometimes requires special treatment.

3. Fill in the `dp` grid data "in order" according to an example.

- The "recursive formula" is the core of the "dynamic programming" algorithm. But the "recursive formula" is obscure. If you want to get it, you need to make a table and use data to inspire yourself.

- If the original example is not good enough, you need to redesign one yourself.

- According to the example, fill in the `dp` grid data "in order", which is very important because it determines the traversal order of the code.

- Most of the time, from left to right, from top to bottom. But sometimes it is necessary to traverse from right to left, from bottom to top, from the middle to the right (or left), such as the "palindrome" problems. Sometimes, it is necessary to traverse a line twice, first forward and then backward.

- When the order is determined correctly, the starting point is determined. Starting from the starting point, fill in the `dp` grid data "in order". This order is also the order in which the program processes.

- In this process, you will get inspiration to write a "recursive formula". If you can already derive the formula, you do not need to complete the grid.

4. Based on the `dp` grid data, derive the "recursive formula".

- There are three special positions to pay 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.

- When operating "two swappable arrays", due to symmetry, we may need to use `dp[i - 1][j]` and `dp[i][j - 1]` at the same time.

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

- Focus on analyzing those values that are not as expected.

After reading the above, do you feel that "dynamic programming" is not that difficult? Try to solve this problem. 🤗

The typical "0/1 knapsack problem" means that each "item" can only be used once to fill the "knapsack". "Items" have "weight" and "value" attributes. Find the maximum value of "items" that can be stored in the "knapsack".

Its characteristics are: there is a **set of numbers**, each number can only be used once, and through some calculation, **another number** is obtained. The question can also be turned into whether it can be obtained? How many variations are there? And so on.

Because "0/1 Knapsack Problem" belongs to "Dynamic Programming", I will explain it in the pattern of "Dynamic Programming".

1. Determine what each value of the array `dp` represents.

- Prefer **one-dimensional rolling array** because the code is concise.

- Determine what is "item" and what is "knapsack".

- If `dp[j]` is a boolean value, then `dp[j]` indicates whether the `sum` of the first `i` items can get `j`.

- If `dp[j]` is a numerical value, then `dp[j]` indicates the maximum (or minimum) value that `dp[j]` can reach using the first `i` items.

2. Initialize the value of the array `dp`.

- Determine the size of the "knapsack". It is necessary to add 1 to the size of the knapsack, that is, insert `dp[0]` as the starting point, which is convenient for understanding and reference.

- `dp[0]` sometimes needs special treatment.

3. According to an example, fill in the `dp` grid data "in order".

- First in the outer loop, **traverse the items**.

- Then in the inner loop, **traverse the knapsack size**.

- When traversing the knapsack size, since `dp[j]` depends on `dp[j]` and `dp[j - weights[i]]`, we should traverse the `dp` array **from right to left**.

- Please think about whether it is possible to traverse the `dp` array from `left to right`?

4. According to the `dp` grid data, derive the "recursive formula".

- If `dp[j]` is a boolean value:

```cpp

dp[j] = dp[j] || dp[j - items[i]]

```

- If `dp[j]` is a numeric value:

```cpp

dp[j] = min_or_max(dp[j], dp[j - weights[i]] + values[i])

```

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

`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.

1. Determine the meaning of each value of the array `dp`.

2. Initialize the value of the array `dp`.

3. Fill in the `dp` grid data "in order" according to an example.

4. Based on the `dp` grid data, derive the "recursive formula".

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

1. Determine the meaning of each value of the array `dp`.

- First determine whether `dp` is a one-dimensional array or a two-dimensional array. A `one-dimensional rolling array` means that the values ​​of the array are overwritten at each iteration. Most of the time, using `one-dimensional rolling array` instead of `two-dimensional array` can simplify the code; but for some problems, such as operating "two swappable arrays", for the sake of ease of understanding, it is better to use `two-dimensional array`.

- Try to use the meaning of the `return value` required by the problem as the meaning of `dp[i]` (one-dimensional) or `dp[i][j]` (two-dimensional). It works about 60% of the time. If it doesn't work, try other meanings.

- Try to save more information in the design. Repeated information only needs to be saved once in a `dp[i]`.

- Use simplified meanings. If the problem can be solved with `boolean value`, don't use `numeric value`.

2. Initialize the value of the array `dp`. The value of `dp` involves two levels:

1. The length of `dp`. Usually: `condition array length plus 1` or `condition array length`.

2. The value of `dp[i]` or `dp[i][j]`. `dp[0]` or `dp[0][0]` sometimes requires special treatment.

3. Fill in the `dp` grid data "in order" according to an example.

- The "recursive formula" is the core of the "dynamic programming" algorithm. But the "recursive formula" is obscure. If you want to get it, you need to make a table and use data to inspire yourself.

- If the original example is not good enough, you need to redesign one yourself.

- According to the example, fill in the `dp` grid data "in order", which is very important because it determines the traversal order of the code.

- Most of the time, from left to right, from top to bottom. But sometimes it is necessary to traverse from right to left, from bottom to top, from the middle to the right (or left), such as the "palindrome" problems. Sometimes, it is necessary to traverse a line twice, first forward and then backward.

- When the order is determined correctly, the starting point is determined. Starting from the starting point, fill in the `dp` grid data "in order". This order is also the order in which the program processes.

- In this process, you will get inspiration to write a "recursive formula". If you can already derive the formula, you do not need to complete the grid.

4. Based on the `dp` grid data, derive the "recursive formula".

- There are three special positions to pay 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.

- When operating "two swappable arrays", due to symmetry, we may need to use `dp[i - 1][j]` and `dp[i][j - 1]` at the same time.

5. Write a program and print the `dp` array. If it is not as expected, adjust it.

- Focus on analyzing those values that are not as expected.

After reading the above, do you feel that "dynamic programming" is not that difficult? Try to solve this problem. 🤗