入门
在知乎上看到徐凯强 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;
}
