力扣（213.337）补8.3

213.打家劫舍‖

不会。。这种需俩俩不想邻的问题头一次见。dp（i）与dp（i-2）有关。

int f(int *nums,int start,int end){

    int dp[end+1];

    memset(dp,0,sizeof(dp));

    dp[start]=nums[start],dp[start+1]=fmax(nums[start],nums[start+1]);

    for(int i=start+2;i<=end;i++){

        dp[i]=fmax(dp[i-2]+nums[i],dp[i-1]);

    }

    return dp[end];

 

}

int rob(int* nums, int numsSize){

    if(numsSize==1)

    return nums[0];

    if(numsSize==2)

    return fmax(nums[0],nums[1]);

    return fmax(f(nums,0,numsSize-2),f(nums,1,numsSize-1));

 

}

337.打家劫舍Ⅲ

开始用C++刷题了，而且最近还要试着准备一下程序设计比赛。这题就是树形dp喽。

 

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 * int val;

 * TreeNode *left;

 * TreeNode *right;

 * TreeNode() : val(0), left(nullptr), right(nullptr) {}

 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

 

class Solution {

public:

    

        unordered_mapf,g;

        void dfs(TreeNode*root){

    if(!root){

        return ;

    }

    dfs(root->left);

    dfs(root->right);

    f[root]=root->val+g[root->left]+g[root->right];

    g[root]=fmax(f[root->left],g[root->left])+fmax(f[root->right],g[root->right]);

} 

int rob(TreeNode* root) {

    dfs(root);

    return fmax(g[root],f[root]);

    }

};