问题描述
给定n个非负整数表示每个宽度为1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水？
图1.1 问题示意图
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
解决方案
首先来理解题意，3能接到水是因为左边最高高度是1右边最高高度是3原本高度是零，可以得到在3的位置能接到水的量是左右最高中最小的减去原本的，然后把所有能接到的水合起来就是答案。
1.普通代码（暴力遍历但超时）
def trap(height): ans = 0 for i in range(len(height)): max_left, max_right = 0, 0 # 寻找 max_left for j in range(0, i): max_left = max(max_left, height[j]) # 寻找 max_right for j in range(i, len(height)): max_right = max(max_right, height[j]) if min(max_left, max_right) > height[i]: ans += min(max_left, max_right) - height[i]
return ans height=[0,1,0,2,1,0,1,3,2,1,2,1] print(trap(height)) |
2.动态规划代码
上述题意符合动态规划的3要素优子结构、边界和状态转移，而且在寻找每个下标的左边和右边最高的柱子时，会对柱子进行反复搜索导致复杂度降低，假如使用两个数组lmax和rmax，lmax[i]表示下标i左边最高柱子的高度,rmax[i] 表示下标i右边最高柱子的高度，很明显，只需要一趟遍历就可以得到结果。这样由于避免了重复计算，就避免了超时。
def trap(height): #边界条件 if len(height)<3: return 0 n=len(height) lmax=[0]*n rmax=[0]*n ans=0 #初始化左右峰 lmax[0]=height[0] rmax[n-1]=height[n-1] #储存左右峰 for i in range(1,n): lmax[i]=max(height[i],lmax[i-1]) for j in range(n-2,-1,-1): rmax[j]=max(height[j],rmax[j+1]) #遍历比较每个位置可以存多少水 for k in range(n): if min(rmax[k],lmax[k])>height[k]: ans+=min(rmax[k],lmax[k])-height[k] return ans height=[0,1,0,2,1,0,1,3,2,1,2,1] print(trap(height)) |
结语
综上所述，只要具备以上三要素的问题均可以采用动态规划的策略进行求解，动态规划可以有效的减少代码的时间复杂度提高代码可读性，是我们编程的好帮手，要熟练掌握。
