# DP - Optimization 2D to 1D

How to optimize DP solutions from `2D`

array to `1D`

?. Take the most classic `01 knapsack`

problem for example.

1 | weights = [1, 3, 4] |

- When we are using
`2D`

array, the deduction is`dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])`

.

The state of`[i][...]`

is only related to the state of`[i-1][...]`

. Then, it’s easy to realize that we can use`dp[j]`

to represent our last iteration result, so we can save some spaces.- Our deduction becomes
`dp[j] = max(dp[j], dp[j-weights[i]] + values[i])`

.

- Our deduction becomes
- When we iterate through
`j`

, be careful to use`reversed`

order on`j`

to avoid repetitive calculations.- For example, for
`j = 1`

,`dp[1] = max(dp[1], dp[1 - weight[0]] + values[0]) = 15`

. (dp[] is initialized as`0`

). - When
`j = 2`

,`dp[2] = max(dp[2], dp[2 - weight[0]] + values[0]) = 15 + 15 = 30`

. - As you can see, we added
`item 0`

twice. - We can avoid this by iterating
`reversely`

because then we can be sure that`dp[j - weight[i]]`

are definitely`not calculated`

yet, so we won’t use it twice.

- For example, for