公司建设网站的意义,海口网站建设服务公司,建站平台哪个最好,wordpress 返回顶部功能198.打家劫舍
思路#xff1a;不能偷相邻的两家。首先确定dp数组及其下标含义 dp[i]表示i之前(包含i)可以投的最大金额。确定递推公式#xff0c;当前dp[i]与前两个索引有关#xff0c;如果偷当前节点 dp[i] dp[i-2]nums[i].如果不偷当前节点dp[i] dp[i-1]#xff0c;所…198.打家劫舍
思路不能偷相邻的两家。首先确定dp数组及其下标含义 dp[i]表示i之前(包含i)可以投的最大金额。确定递推公式当前dp[i]与前两个索引有关如果偷当前节点 dp[i] dp[i-2]nums[i].如果不偷当前节点dp[i] dp[i-1]所以dp[i] max( dp[i-2]nums[i], dp[i-1])。初始化dp数组dp[0] nums[0]. dp[1]max(nums[0],nums[1]). 遍历顺序从小到大。打印dp数组可以用于debug。
class Solution {
public:int rob(vectorint nums) {//确定dp数组及其下标的含义 dp[i]表示i之前包含i能投的最大金额//递推公式 i当前与i前面的两个索引有关 dp[i] max(dp[i-2]value[i],dp[i-1])。即偷当前i和不偷当前i两种情况//初始化dp[0] value[0]; dp[1] max(value[0],value[1]).//遍历顺序从小到大遍历//打印dp数组用于debugif(nums.size()0){return 0;}if(nums.size()1){return nums[0];}vectorint dp(nums.size(),0);dp[0] nums[0];dp[1] max(nums[0],nums[1]);for(int j 2;jnums.size();j){dp[j] max(dp[j-2]nums[j],dp[j-1]);}return dp[nums.size()-1];}
};
213.打家劫舍II
思路此时数组为一个环形相比于打家劫舍I需要考虑首位是否相邻偷取的情况因此将环形结构展开成两个线性结构一个包含头元素不包含尾元素一个包含尾元素不包含头元素这样一定不会首尾同时包含。选择两种情况的最大值。
class Solution {
public:int rob(vectorint nums) {//划分成两种情况 一种情况包含头元素不包含尾元素 一种情况包含尾元素不包含头元素//这样两种情况就不会首尾相邻vectorint dp1(nums.size()-1,0);vectorint dp2(nums.size()-1,0);if(nums.size()1){return nums[0];}if(nums.size()2){return max(nums[0],nums[1]);}dp1[0] nums[0];dp1[1] max(nums[0],nums[1]);for(int i 2;inums.size()-1;i){dp1[i] max(dp1[i-2]nums[i],dp1[i-1]);}dp2[0] nums[1];dp2[1] max(nums[1],nums[2]);for(int j 2;jnums.size()-1;j){dp2[j] max(dp2[j-2]nums[j1],dp2[j-1]);}return max(dp1[nums.size()-2],dp2[nums.size()-2]);}
};
337.打家劫舍III
思路这道题是二叉树dp问题即利用了动态规划还需要利用递归二叉树。现确定递归三部曲首先确定递归函数的输入参数和返回类型然后确定终止条件当节点为NULL时返回{00}。第一个元素代表不偷这个节点的最大金额第二个元素代表偷了这个节点后的最大金额。确定单层递归逻辑后序遍历左右中如果偷当前节点那么val1 root-valdpleft[0]dpright[0]不能偷子节点。如果不偷当前节点可以选择偷或者不偷子节点val2 max(dpleft[0],deleft[1])max(dpright[0]dpright[1]). return {val2,val1};
/*** 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://递归函数//递归三部曲 确定递归函数的参数和返回类型vectorint traversal(TreeNode* root){//确定终止条件if(rootNULL){return {0,0};}//确定单层递归逻辑vectorint leftdp traversal(root-left);vectorint rightdp traversal(root-right);//偷当前节点int val1 root-valleftdp[0]rightdp[0];//不偷当前节点int val2 max(leftdp[0],leftdp[1])max(rightdp[0],rightdp[1]);return {val2,val1};}int rob(TreeNode* root) {vectorint result traversal(root);return max(result[0],result[1]);}
};
收获
打家劫舍的一天dp数组的含义为包含当前节点无论偷不偷的最大金额根据相邻的关系推出递推公式。
二叉树dp问题既要考虑递归三部曲又要考虑dp五部曲。
