leecode42 DP

本文主要是介绍leecode42 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

自己的暴力想法,把图形看成一个个碗,一段一段地算,错误示例

class Solution {
public:int trap(vector<int>& height) {int s = height.size();int sum = 0,kk=1;int flag = 0;int p1 = -1, p2 = -1;for (int i = 1; i < s; i++) {cout<<p1<<endl;if (p1 >= 0 && flag) {if (height[i] >=height[p1]) // 找到了高于最左边的值,短板效应,后面即便更大该曲线的水也不变{for (int j = p1 + 1; j < i; j++) {sum += height[p1] - height[j];}p1 = -1;flag = 0;kk=1;} else if (height[i] < height[i - 1]) // 该段最高点到了{for (int j = p1 + 1; j < i - 1; j++) {sum += height[i - 1] - height[j];}p1 = -1;flag = 0;kk=1;} else if (i == s - 1) //{for (int j = p1 + 1; j < i; j++) {sum += height[i] - height[j];}}if (p1 >= 0 && height[i] <= height[i - 1]) {p2 = i;} else if (p1 >= 0 && height[i] > height[i - 1]) {flag = 1;}if (height[i] < height[i - 1]&&kk) {p1 = i - 1;kk=0;}}return sum;}
};

主要问题在于,不好判断一段盛水区间什么时候结束,蠢麻了,然后想到DP,前面错误想法的前提上肯定想不明白的

题解思路是这样的,每一列盛水是由该列左右两侧最大值的较小值决定的,较小值减去该列值即为该列盛水量,所以建两个数组,分别存左右最大,然后计算即可

class Solution {
public:int trap(vector<int>& height) {int s=height.size();int sum=0;int o=height[0],p=height[s-1];vector<int>kk;for(int i=0;i<s;i++){o=max(o,height[i]);kk.push_back(o);}for(int i=s-1;i>=0;i--){p=max(p,height[i]);kk[i]=min(kk[i],p);sum+=kk[i]-height[i];}return sum;}
};

这篇关于leecode42 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---