The definition of dynamic programming int the textbook is solving a complex problem by breaking it down into simple problems. However, I think it is much more like mathematical induction, proving the basic conclusion and proving the relationship of the complex result and the simple result.

Most dynamic programming problems are in 1D and 2D.

• For the easy and medium problems, the 1D dynamic programming is mostly based on the intervals starting at the origin and ending at any indices, and the 2D dynamic programming is mostly based on the areas staring at the origin and ending at any point.
• For the hard problems, there could be 2D and 3D dynamic programmings. The 2D dynamic programming can be based on the intervals starting and ending at any indices. 

Here are 2 examples of dynamic programming based on intervals:

312. Burst Balloons My solution.

First of all, as the bursting can be in any order, we cannot use 1D dp based on intervals starting at the origin. Consequently, we shall use 2D dp based on intervals starting at any indices.

Secondly, we notice that based on the order of bursting, the left side and the right side of the target balloons can change. Furthermore, the left side and right side of the target intervals can change. This will make the result of the smaller intervals unusable for the larger intervals.

To fix this issue, we take the following method:

• assume the left side and the right side of the interval are not burst
• try all the balloons as the last one to burst
• calculate the reward of bursting the left subinterval and the right subinterval, plus the reward of bursting this balloon with the left side and right side of the entire interval.

In this method, the entire interval and subintervals have fixed left and right side, the result won’t change and are reusable.

The coding part is a 2D dp. dp[i][j] stands for the maximum reward of bursting all the balloons between i (inclusive) and j (inclusive). The dp needs to start small intervals and concludes to large intervals, as the current result is build based on the previous result of small intervals.

1000. Minimum Cost to Merge Stones My solution.

Similarly, the merging can be in any order, we shall use 2D dp based on intervals starting at any indices.

Secondly, we notice that based on the order of merging, the left stones can change. To fix this issue, we take the following method:

• assume all the intervals are merged as much as possible
• try all the left subintervals that could be merged into the first stone
• calculate the reward of merging the left subinterval and the right subinterval, and the rewards of merging the left stones if then can be merged.

In this method, the entire interval will always be merged as much as possible and the merge will always happen with stones of size K. Even though we don’t know what stones are left at the final merge but we do know that the sum of the stones will be the sum of the interval at the original state.

The coding part is a 2D dp. Similar to 312.