### PROBLEM LINK:

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Dynamic Programming

### PROBLEM:

Given a **K**-steps stair, try to merge some adjacent steps to get **M**-steps remained such that the total volume added is minimum.

### EXPLANATION:

We can only merge consecutive steps in this problem. This gives us the intuition of dynamic programming.

Let’s denote the cost of merging steps in [**L**, **R**] as **cost[L][R]**. Clearly, we can brute-forcely build this array in O(**K**^3) time by definition, because **K** is only at most 500 here.

And let **f[i][j]** states the minimum cost of merging the first **i** steps into **j** steps. Then, we can try to deal with the problem using the following recursion.

```
f[i][j] = min { f[k][j - 1] + cost[k + 1][i] } for all 0<= k < i.
```

Initially, by definition, we have

```
f[0][0] = 0, f[0][j > 0] = + infinite.
```

Therefore, we can solve this problem in O(**K**^3).

In fact, we can also further optimize this algorithm to O(K^2).

We can observe that **cost[L][R]** can be calculated by some values (e.g. prefix sum of heights, lengths, areas) of **L** and **R** separately. More specifically,

```
cost[L][R] = (SHeight[R] - SHeight[L - 1]) * (SLeng[R] - SLeng[L - 1]) - (SArea[R] - SArea[L - 1])
```

About the dynamic programming, we should observe that **f[i][j]** only depends on **f[k < i][j - 1]**. Furthermore, **f[i][j]** can be expressed in the minimum of **A _{k} * f[k][j-1] + B_{k}**. If we first loop over

**j**and then enumerate

**i**from small to large, due to the monotonic property of

**A**, we can maintain a double-ended-queue of

_{k}**k**ordered by the

**A**(pop out the invalid

_{k}**k**). Every

**k**will enter or leave this queue at most once. Because we can then find the minimum in O(1) time, the total complexity is reduced to O(

**K**^2).