题目
最小步骤收集硬币
有许多相邻排列的硬币堆。我们需要以最少的步骤收集所有这些硬币，在一个步骤中，我们可以收集一个水平线的硬币或垂直线的硬币，收集的硬币应该是连续的。
输入描述
输入第一行整数N表示硬币堆的数量
输入第二行有N个整数分表表示硬币堆的高度
输出描述
采集所有硬币需要最小步骤
样例输入
5
2 1 2 5 1
样例输出
4
解析
第一行表示有五堆硬币，
第二行表示第一堆有两枚硬币，第二堆一枚硬币，依此类推。
取硬币需要4步，如图所示，取硬币的步骤用不同颜色的线段表示。
问题分析和算法设计思路
基本思路：分治法
从下方删除水平线总是有益的，于是以左图方式对硬币对进行分治，将一个原问题划分为 3 个子问题，递归求解。但我们还有纵向收集硬币的方法，每次都取两种方案的最小值。
左图：从下方删除水平线
右图：一直纵向取完所有硬币
有过的一些疑问
1、既然已经对问题分治了，干嘛还要和纵向取完所有硬币的情况进行比较？
分别用分治和纵向取硬币的思路考虑，只有一列硬币的情况：
2、既然直接一直分治不是最优，还要和纵向取完所有硬币的情况比较，那分治和纵向取完就能保证最优了吗？会不会有其它更好的策略？比如“先纵取硬币最多的一列”会不会更好？
比较严谨的证明我也没想出来。
不过我们也许不必太纠结先取行还是先取列的问题，从最初题目的图可以看到，它只是用线条将这些硬币划分成了 4 部分，而线条之间是没有顺序的。也就是说一些看似不同的决策其实是等价的。
3、在问题社区提问：以最小的步骤收集所有硬币，如何证明该分治算法的正确性？
问题链接：https://ask.csdn.net/questions/7810917
有个博主回答如下，可以参考
首先你要审题，下方是重力方向，所以下方的硬币数量必然比上方的多，硬币不能悬空
而取硬币一共就两种取法，要么取一横排，要么取一竖列
如果先按竖列取，会把最下面的横排截断，所以显然不是最好的方法
而先按横排取，不会截断其它行列
那么你不从长的开始取，难道从最短的开始取吗
算法实现
参考代码：https://www.imangodoc.com/83929.html
#include <bits/stdc++.h> using namespace std; int minStepsRecur(int height[], int l, int r, int h) { if (l >= r) return 0; int m = l; for (int i = l; i < r; i++) if (height[i] < height[m]) m = i; return min(r - l, minStepsRecur(height, l, m, height[m]) + minStepsRecur(height, m + 1, r, height[m]) + height[m] - h); } int minSteps(int height[], int N) { return minStepsRecur(height, 0, N, 0); } int main() { int N = 0; cin >> N; int *height = new int[N]; for(int i = 0; i < N; i++) { cin >> height[i]; } cout << minSteps(height, N) << endl; return 0; }
运行结果
算法分析
时间复杂度：O ( N ) \Omicron (N)O(N)，N 为硬币堆的数量
