算法：动态规划(DP)入门实践
入门
在知乎上看到徐凯强 Andy的答案后感觉入门了
实践
题目：仅包含0/1的矩阵，求其中最大的全1方阵（不能是矩形）的边长
题解：matrxi[100][100]表示0/1矩阵，dp[i][j]表示：
以matrix[i][j]为右下角，边长最大为min(i,j)的，最大全1方阵的边长， if(matrix[i][j]==0) { dp[i][j]=0; } if(matrix[i][j]==1) { if(dp[i-1][j]==1&&dp[i][j-1]==1) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=1; } } 最后dp数组中最大的值即所求的边长题目：https://leetcode.com/problems/trapping-rain-water/description/ Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
题解：https://leetcode.com/problems/trapping-rain-water/solution/ 核心思想：维护一个区间，当区间缩小时看看是否有一边下降，如果下降则盛雨量增加，否则向内移动短边。
// https://leetcode.com/problems/trapping-rain-water/solution/
// Approach #4 Using 2 pointers [Accepted]
int trap(vector<int>& height)
{
int left = 0, right = height.size() - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
++left;
}
else {
height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
--right;
}
}
return ans;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.09.02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录