目录
- 题目
- 问题
题目
最小步骤收集硬币
有许多相邻排列的硬币堆。我们需要以最少的步骤收集所有这些硬币，在一个步骤中，我们可以收集一个水平线的硬币或垂直线的硬币，收集的硬币应该是连续的。
输入描述
输入第一行整数N表示硬币堆的数量
输入第二行有N个整数分表表示硬币堆的高度
输出描述
采集所有硬币需要最小步骤
样例输入
5
2 1 2 5 1
样例输出
4
解析
第一行表示有五堆硬币，
第二行表示第一堆有两枚硬币，第二堆一枚硬币，依此类推。
取硬币需要4步，如图所示，取硬币的步骤用不同颜色的线段表示。
问题
参见：https://verytoolz.com/blog/62dc864e1a/
我们可以使用分治法来解决这个问题。我们可以看到，从下方移除水平线总是有益的。假设我们在递归步骤中处理从 l 索引到 r 索引的堆栈，每次我们将选择最小高度，删除那些水平线，之后堆栈将分为两部分，l 到最小值和最小值 + 1 到 r 和我们将在这些子数组中递归调用。另一件事是我们也可以使用垂直线收集硬币，因此我们将在递归调用的结果和 (r - l) 之间选择最小值，因为使用 (r - l) 垂直线我们总是可以收集所有硬币。每次我们调用每个子数组并找到其中的最小值时，解决方案的总时间复杂度将为 O(N2)
为什么从下方移除水平线总是有益的呢？
又或者说，为什么在递归调用的结果和 (r - l) 之间选择最小值得到的是原问题的最小值呢？如何保证不会存在其它步数更小的步骤序列？
