目录

题目

最小步骤收集硬币
有许多相邻排列的硬币堆。我们需要以最少的步骤收集所有这些硬币，在一个步骤中，我们可以收集一个水平线的硬币或垂直线的硬币，收集的硬币应该是连续的。
输入描述
输入第一行整数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) 之间选择最小值得到的是原问题的最小值呢？如何保证不会存在其它步数更小的步骤序列？

首先你要审题，下方是重力方向，所以下方的硬币数量必然比上方的多，硬币不能悬空
而取硬币一共就两种取法，要么取一横排，要么取一竖列
如果先按竖列取，会把最下面的横排截断，所以显然不是最好的方法
而先按横排取，不会截断其它行列
那么你不从长的开始取，难道从最短的开始取吗

// Java Code to Collect all coins in
// minimum number of steps
import java.util.*;
  
class GFG {
  
    // recursive method to collect coins from
    // height array l to r, with height h already
    // collected
    public static int minStepsRecur(int height[], int l,
                                           int r, int h)
    {
        // if l is more than r, no steps needed
        if (l >= r)
            return 0;
  
        // loop over heights to get minimum height
        // index
        int m = l;
        for (int i = l; i < r; i++)
            if (height[i] < height[m])
                m = i;
  
        /* choose minimum from,
            1) collecting coins using all vertical
            lines (total r - l)
            2) collecting coins using lower horizontal
            lines and recursively on left and right
            segments */
        return Math.min(r - l,
                        minStepsRecur(height, l, m, height[m]) + 
                        minStepsRecur(height, m + 1, r, height[m]) +
                        height[m] - h);
    }
  
    // method returns minimum number of step to
    // collect coin from stack, with height in
    // height[] array
    public static int minSteps(int height[], int N)
    {
        return minStepsRecur(height, 0, N, 0);
    }
  
    /* Driver program to test above function */
    public static void main(String[] args)
    {
  
        int height[] = { 2, 1, 2, 5, 1 };
        int N = height.length;
  
        System.out.println(minSteps(height, N));
    }
}
  
// This code is contributed by Arnav Kr. Mandal.