https://www.luogu.org/problemnew/show/P1941
\(5 \leq n,m \leq 10, k = 0\)
DFS(i,j,k) 表示横坐标为 \(i\)，高度为 \(j\)，走了 \(k\) 步
暴力 DFS 即可，只要始终保持 \(j > 0\)， 时间复杂度 \(O(4^nm)\)
\(5 \leq n \leq 20, 5 \leq m \leq 10\)
如果仍然暴力 DFS，时间复杂度无法承受。
这个问题具有明显的 最优子结构 和 重叠子问题 的特征，可以考虑动态规划或者记忆化搜索；
状态：\(f[i][j]\) 表示横坐标为 \(i\)，高度为 \(j\) 的最小步数；转移较为复杂，建议考虑 “我为人人” 型动态规划。
转移：\(f[i][j] = Min\{ f[i-1][j+y[i-1]], f[i-1][j-kx[i-1]]+k \}\)
需要注意的是，\(f[i][m]\) 需要特殊的转移：\(f[i][m] = Min\{f[i-1][k] + \lceil \frac{m-k}{x[i-1]} \rceil \} (k \not= m)，Min\{f[i-1][m] + 1\}\)。
这是一个 \(2D/1D\) 动态规划，时间复杂度 \(O(nm^2)\).
由于有特殊性质，50pts 的动态规划时间复杂度是 \(O(nm)\).
有大佬告诉我这个 DP 式子很像完全背包，所以可以用完全背包的方法优化；
这个方法以后再补，先来讲讲我的方法：
优化的动机主要是 重复 和 不必要 ，观察上面那个 DP 式子，可以发现 \(f[i][j]\) 和 \(f[i][j-x[i-1]]\) 的转移有大量重复，我们展开转移式子的第 2 项，可以得到：
\[
f[i][j] <= (Min)f[i-1][j-x[i-1]] + 1 \f[i-1][j-2x[i-1]] + 2 \f[i-1][j-3x[i-1]] + 3 \\cdots \f[i-1][j-kx[i-1]] + k \\f[i][j-x[i-1]] <= (Min)f[i-1][j-2x[i-1]] + 1\f[i-1][j-3x[i-1]] + 2 \f[i-1][j-4x[i-1]] + 3 \\cdots \f[i-1][j-kx[i-1]] + k-1 \\]
可以看到，\(f[i][j]\) 的转移和 \(f[i][j-x[i-1]]\) 的转移第 \(2\) 项就相差了 \(1\) 项，其它转移都加了 \(1\)，这对最小值是没有影响的。
那么不妨用 \(g[i][j]\) 表示 \(Min\{f[i-1][j-kx[i-1]]+k\}\)，就可以得到新的转移：
\[
g[i][j] = min\{f[i-1][j-x[i-1]]+1, g[i][j-x[i-1]]+1\} \f[i][j] = min\{f[i-1][j+y[i-1]], g[i][j]\}
\]
这样就可以在 \(O(nm)\) 的时间内完成 DP 了。
原文：https://www.cnblogs.com/YJZoier/p/9807256.html