题目

最小步骤收集硬币
有许多相邻排列的硬币堆。我们需要以最少的步骤收集所有这些硬币，在一个步骤中，我们可以收集一个水平线的硬币或垂直线的硬币，收集的硬币应该是连续的。
输入描述
输入第一行整数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;
}

运行结果

算法分析

时间复杂度：$\mathrm{O}(N)$，N 为硬币堆的数量