[TOC]

本文正在参与掘金团队号上线活动，点击查看大厂春招职位

程序员如果仅满足curd的话，那么35岁危机很快就会到来。在大学期间学校主打的应该也都是算法思维。今天我们已大学里学的一个理论为基础展开讨论—动态规划

理论

将一个大问题细化为子问题。即转换经过一层一层的细化最终转为话小问题或者说转换为已知解。
话不多说，我们直接已leetcode42–接雨水问题展开

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]

输出：9

提示：

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

思路分析

上面是笔者的提交记录，在速度上还是蛮快且没有占用太多内存。速度上目前是leetcode中java程序超越100%；内存使用上最好的一次是超越98%；下面我们先来分析一下解题思路
学习过动态规划的都知道正常的动态规划有几步骤。

确定转换方程

因为动态规划就是将大问题分解成小问题。如果我想要获取100块钱。假设面值只有1元，那么我想活得100元就必须先获得99元。从100到99的过程就是我们分解的过程。依次类推我们最终只需要获取到1元就可以推倒出100元了。这个过程和递归还是有区别的。今天我们不做赘述。
在接雨水题目中我们当前接水量是受后面柱子的影响的。
为了后续方便演示我们约定如下称谓

简称	含义
Zn	第几根柱子；即图中的坐标
Sn	表示截止到第n根柱子，整体形成的水池容量
SDn	表示当前第n根柱子垂直方向的水量
Zmax	表示截止到目前出现的最高的柱子的高度
Sm,n	表示第m到第n块柱子形成的水池

就像题目中一样在走到第六块时，此时Z6=0 .表示第六块的柱子所形成的水池是0 。但是当第七块是会与第六块和第五块形成水池。
所以假设Fx表示从1开始到第x块柱子形成的水池容量。

确定初始值

这道题的初始值考虑不是很多。第一块很明显是0 ，即S0=0

从小到大依次计算

第一步平地高楼。S0=0

第一步，我们直接从第二根柱子开始，此时没有最高柱子是不会形成水池的。我们计算结果S2=0;

然后我们将指针移动到第三根柱子，Z3=0我们理解为平地，平地是不会形成水池的。所以S3=S2=0;

next，我们走到了第四根柱子，Z4=2,当前最高的柱子是Z2=1;注意这里Z4还没有加入最高柱子竞争中。所以Zmax=Z2=1。按照我们的推导公式。在[Z2~Z4)中不存在不低于Z4的柱子,所以S4=S2+S4,2
S4,2表示第二块到第四块形成的水池容量S4,2=(4-2-1)*min(Z2,Z4)-柱子容量=1
所以S4=0+1=1;

现在指针走到了第五根柱子，第五根和第四根之间没有空隙，所以S5=S4=1;

在第三根柱子的时候我们得出理论，平地是不可能有水池形成的。所以这里第六根柱子直接忽略。。
S6=S5=1

当前最高的柱子是Z4。在Z4~Z7中存在Z5是不低于Z7的。所以S7=S5+S7,5
S7,5表示第五根到第七根的水池=1
S7=1+1=2.

Z8=3。在Zmax~Z8中没有不低于Z8的。所以直接与Zmax形成水池。
S8=S4+S8,4
S8,4=(8-4-1)*min(Zmax,Z8)-sum(Zmax+1,Z7)=3*2-(1+1)=6-2=4
S8=1+4=5

第八跟和第九根没有缝隙，所以没有水池。
S9=S8=5

S10和S9没有缝隙，所以也没有水池
S10=S9=6

在第11根柱子时，我们Zmax=Z8.我们找到了Z9不低于Z11。所以S11=S8+S11,9=5+1=6
所以最终答案就是6 。
到这里我将整个过程已动画的形式展现出来。应该可以理解到动态规划的意思了吧。
下面我们直接看看代码实现吧。

AC代码

为了方便读者演示效果。下面的程序是完整的代码。只需要复制过去导入包后直接运行即可。


public int trap(int[] height) {
    if (height.length == 0) {
        return 0;
    }
    int[] result = new int[height.length];
    int heighMaxIndex = 0;
    for (int i = 1; i < height.length; i++) {
        if (height[i] == 0) {
            result[i] = result[i - 1];
            continue;
        }
        int secondMaxIndex = i-1;
        boolean flag = false;
        for (int j = i - 1; j >= heighMaxIndex; j--) {
            if (height[j] >= height[i]) {
                //截至柱
                int x =i-j-1;
                int y = getHeightCrossX(height,j,i);
                result[i] = result[j] + x * height[i] - y;
                flag=true;
                break;
            }
            if (height[j] > height[secondMaxIndex]) {
                secondMaxIndex = j;
            }
        }
        if (flag) {
            continue;
        }
        int y = getHeightCrossX(height, secondMaxIndex, i);
        result[i]=result[secondMaxIndex]+height[secondMaxIndex]*(i-secondMaxIndex-1)-y;
        if (height[heighMaxIndex] < height[i]) {
            heighMaxIndex=i;
        }
    }
    return result[result.length-1];
}

private int getHeightCrossX(int[] height,int j, int i) {
    int y = 0;
    for (int k = j + 1; k < i; k++) {
        y += height[k];
    }
    return y;
}

public static void main(String[] args) {

    LeetCode42 leetCode = new LeetCode42();
    System.out.println(leetCode.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));

}

总结

接雨水问题是典型的动态规划问题，只不过他的前一步会受到后面几步的影响。所以我们的推导公式需要找到不受影响的上一步。也就是我们推到中称的最高柱。因为最高柱的形成相当于是一堵墙，墙的左边是受保护的。

学如逆水行舟，不进则退！！！

LeetCode42题动态规划 - 接雨水

理论