动态规划

42. 接雨水">42. 接雨水
暴力法
动态规划

42. 接雨水

暴力法

func trap(height []int)int{
    l :=len(height)
    res :=0
    // 起始位置是第一个，而不是0
    // 结束位置是倒数第二个，而不是倒数第一个
    for i:=1;i<l-1;i++{
        leftMax :=height[i]
        for k:=i-1;k>=0;k--{
            if leftMax<height[k]{
                leftMax = height[k]
            }
        }
        if leftMax<=height[i]{
            continue
        }
        rightMax :=height[i]
        for j:=i+1;j<l;j++{
            if rightMax<height[j]{
                rightMax = height[j]
            }
        }
        if rightMax<=height[i]{
            continue
        }
        minVal := min(leftMax,rightMax)
        water := minVal-height[i]
        res =res+water
    }
    return res
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

1 动态规划所做的事情实质就是减少重复计算，递归或者暴力中一般都会存在大量重复计算，如果我们利用一个小本本的形式记录之前计算的结果是不是就可以节约时间了，也就是变相的空间换时间方式。
2 动态规划所做的事情是什么？，1加100 我们每一步计算结果都记录下来加100 实际上就是前面1-99的结果在加100，就等于有个字典你记录你已经做过的事情的结果，如果再有人问你，你的做法就是翻字典查结果，而不是再重头归零计算，要让计算机产生记忆，而这个记忆就是利用空间存储换取时间，
3 很多动态规划直接告诉你转移方程，这个行为对你学习没有太多的帮助，我对这种方式持中立态度，学习是为了学会捕鱼，而不是快速拿到鱼，如果你都连暴力都没办法写出题解，怎么可能知道暴力中存在哪些重复计算，然后又怎么可能知道对重复计算进行优化了？
4 接雨水问题实质上要处理2个问题，能不能接雨水？能接多少？，这个自己一定要画图，一直强调自己动手实践
5 能不能接雨水实质生活中就这个地方是一个低洼区，人肉眼很容易识别，对于计算机来说不行，你要计算出当前位置左边和右边是不是存在比他高的地方。
6 而解决了能不能存水，能存多少水也会迎刃而解，它是当前位置左右高点的最低值决定的。
7 而暴力法中存在最大的问题就是计算当前位置的左右最高点是存在重复计算的，本来当前位置左边和右边最高值等于当前位置的高度和前一个位置的高度计算结果比较一下就可以得到了，而暴力每次把左右两边都从头在算一遍。自己想想需要这样重复计算吗？
8 通过数组把这些重复计算保存起来就是一种记忆法，对比一下暴力和动态的代码看看是不是在做这个事情。

动态规划实际上就是减少暴力中的重复计算问题。
leftDP 表示i 左边的最大值
rightDP表示以i开始右边的最大值

func trap(height []int)int{
    if len(height)==0{
        return 0
    }
    size :=len(height)
    res :=0
    leftDP :=make([]int,size)
    rightDP :=make([]int,size)
    leftDP[0]= height[0]
    rightDP[size-1] = height[size-1]
    for i:=1;i<size;i++{
        leftDP[i] = max(leftDP[i-1],height[i])
    }
    for i:=size-2;i>=0;i--{
        rightDP[i] = max(rightDP[i+1],height[i])
    }
    for i:=1;i<size-1;i++{
        minHeight := min(leftDP[i],rightDP[i])
        waterVal :=minHeight-height[i]
        res +=waterVal
    }
    return res
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}