leetcode每日一题38

337.打家劫舍II

树形dp
从叶子开始，若偷了孩子，那么父节点就不能被偷
选择金额最高的那条路径
因此是后续遍历，且动规

1. 确定递归函数的参数和返回值
   返回dp数组。参数是当前节点

vector<int> robTree(TreeNode* cur)

确定一下dp数组的定义：
dp[i] i==0 不偷当前节点的最大金额
i==1偷当前节点的最大金额
为什么dp数组只有当前节点，没有其他节点：
因为递归中，系统栈会自动保存每一层递归的参数

2. 确定终止条件
   遇到空节点，自然是偷不偷都是金额0

if(cur==NULL)
	return vector<int> {0,0}

3. 确定遍历顺序
   从叶到根，后序

vector<int> left=robTree(cur->left);
vector<int> right=robTree(cur->right);

4. 确定单层递归的逻辑
   如果偷当前节点，那么左右孩子就肯定没偷过
   如果不偷当前节点，那么左右孩子就可以偷，可以都偷，也可以只偷一个，甚至可以不偷，从这几种方案里选一个最大的就行

dp[0]=max(left[1],left[0])+max(right[0],right[1]);
dp[1]=left[0]+right[0]+cur->val;
return dp;

5. 举例推导dp数组

最后获得代码

class Solution {
public:
    vector<int> robTree(TreeNode* cur){
        vector<int> dp(2,0);
        if(cur==NULL)
            return vector<int> {0,0};
        vector<int> left=robTree(cur->left);
        vector<int> right=robTree(cur->right);
        dp[0]=max(left[1],left[0])+max(right[0],right[1]);
        dp[1]=left[0]+right[0]+cur->val;
        return dp;
        }
    int rob(TreeNode* root) {
        vector<int> result;
        result=robTree(root);
        return max(result[0],result[1]);
    }
};

221.最大正方形

评论区看到的dp技巧

默念一句话“动态规划每一步填表都建立在之前已经填完的表上”；
表的值的意义和你return的值的意义一样（不要多想）！！！
不要考虑初始化边缘（千万不要从dp[0][0]想思路！！！），从中间取一个点，想这个点的值怎么根据它的左边、上边、左上边、左下边的值计算出来！！！

这道题显然一块区域是否为正方形，是可以从其他状态里推导出来的
若在某一个格子里，数值是1，那么它就由它上，左，和左上是否为1决定是否可以组成更大的正方形
上，左，和左上里连续为1的边长最短的值，再加1即可构成以当前格子为右下角的最大正方形
至于为什么选上、左、左上，为了方便遍历从左到右从上到下

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j]为以格子（i,j）为右下角的最大正方形边长
2. 确定递推公式
   dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
3. dp数组如何初始化
   dp[0][j]和dp[i][0]如果为1，那么只能组成边长为1的正方形，如果为0，那么边长为0

for(int i=0;i<matrix.size();i++)
	if(matrix[i][0]=='1')
		dp[i][0]=1;
	else dp[i][0]=0;
for(int j=0;j<matrix[0].size();j++)
	if(matrix[0][j]=='1')
		dp[0][j]=1;
	else dp[0][j]=0;

4. 确定遍历顺序
   从左到右从上到下

for(int i=1;i<matrix.size();i++)
	for(int j=1;j<matrix[0].size();j++)
		if(matrix[i][j]=='1')
			dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
		else dp[i][j]=0;

因为在这里行列都是从1开始的，所以只在第0行/列有数值1的最大尺寸此处没法更新，所以更新一下初始化的代码

for(int i=0;i<matrix.size();i++)
    if(matrix[i][0]=='1'){
        dp[i][0]=1;
        maxSide=1;
    }
    else dp[i][0]=0;
for(int j=1;j<matrix[0].size();j++)
    if(matrix[0][j]=='1'){
        dp[0][j]=1;
        maxSide=1;
    }
    else dp[0][j]=0;

若行/列中有值为1，那么修改此时的最大边长为1
5. 举例推导dp数组

最后得到代码：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxSide=0;
        if(matrix.size()==0||matrix[0].size()==0)
            return 0;
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size()));
        for(int i=0;i<matrix.size();i++)
            if(matrix[i][0]=='1'){
                dp[i][0]=1;
                maxSide=1;
            }
            else dp[i][0]=0;
        for(int j=0;j<matrix[0].size();j++)
            if(matrix[0][j]=='1'){
                dp[0][j]=1;
                maxSide=1;
            }
            else dp[0][j]=0;
        for(int i=1;i<matrix.size();i++){
            for(int j=1;j<matrix[0].size();j++){
                if(matrix[i][j]=='1')
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                else dp[i][j]=0;
                maxSide=max(maxSide,dp[i][j]);
            }
        }
        return maxSide*maxSide;
    }
};