动态规划理论基础
动规五部曲:
- 确定dp数组 下标及dp[i] 的含义。
- 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
- 初始化dp数组。
- 确定遍历顺序:从前到后or其他。
- 打印。
出现结果不正确:
- 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。
- 打印dp日志和自己想的不一样:代码实现细节出现问题。
1. 打家劫舍Ⅲ
参考文档:代码随想录
分析:
树的递归三部曲 结合 动规五部曲:
- 函数的参数和返回值:返回某个节点偷与不偷得到的金额,所以返回值确定是一个长度为2的数组vector<int>。dp数组为vector<int>的长度为2的数组,dp[0]表示当前节点不偷得到的金额,dp[1]表示当前节点偷得到的金额。
- 终止条件:遇到空节点,返回{0, 0}。
- 单层递归的逻辑:判断当前节点到底是偷还是不偷取决于孩子节点不偷+根节点偷 或 根节点不偷+孩子节点偷 得到的最大值,所以用后序遍历,也确定了递推公式。
//计算 节点偷与不偷 得到的金额
vector<int> calRob(TreeNode* cur){
...
//左孩子 偷和不偷 的金额
vector<int> left = calRob(cur->left);
//有孩子 偷和不偷 的金额
vector<int> right = calRob(cur->right);
//递推公式
//偷
int sum1 = cur->val + left[0] + right[0];
//不偷
int sum2 = max(left[0], left[1]) + max(right[0], right[1]);
//返回当前节点偷与不偷得到的金额
return {sum2, sum1};
}
代码:文章来源地址https://www.toymoban.com/news/detail-836848.html
/**
* 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:
int rob(TreeNode* root) {
//树形dp:考虑 树的遍历顺序 和 处理逻辑
//后序遍历(❓)左右孩子是否偷对当前节点是否偷是有影响的
//dp[i]表示这个这个节点偷和不偷的金币值(❓)
vector<int> res = calRob(root);
return max(res[0], res[1]);
}
vector<int> calRob(TreeNode* cur){
if(cur == NULL) return {0,0};
if(cur->left == NULL && cur->right == NULL) return {0, cur->val};
vector<int> left = calRob(cur->left);
vector<int> right = calRob(cur->right);
//偷
int sum1 = cur->val + left[0] + right[0];
//不偷
int sum2 = max(left[0], left[1]) + max(right[0], right[1]);
return {sum2, sum1};
}
};
2. 打家劫舍Ⅱ
参考文档:代码随想录
分析:
房屋之间成环了,相邻两间房子都偷会使警报器响,所以首偷了尾就绝不能偷,首不偷尾可以偷。回顾打家劫舍Ⅰ,dp[i]的含义是考虑[0, i]房子可以偷窃的最大金额,dp[i] = max(dp[i-1], dp[i-2]+nums[i]),根据递推公式,在决定第i间房子可以偷窃的最大金额是受到i-1和i-2的影响的,再往前推i-1受到i-2和i-3的影响,递推下去dp[i]是受到[0-i-1]之前的房子的影响,有可能这些房子会偷,有可能不偷,但是是影响dp[i]的数值的。所以为了避免首对尾的影响,不将首和尾的房间房子一起。
确定动态规划的区间是 [0, nums.size()-2] 和 [1, nums.size()-1] ,返回两个区间得到的最大值。
接下来讨论dp五部曲:
- dp[i]含义:考虑[0, i]的房子可以偷窃的最大金额。
- 递推公式:dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
- 初始化:dp[0] = nums[0], dp[1] = max(dp[0], dp[1]);
- 遍历顺序:从前到后更新。
代码:
class Solution {
public:
//计算从 begin到end 闭区间偷的金额最大值
int calRob(vector<int>& nums, int begin, int end){
vector<int> dp(nums.size(), 0);
dp[begin] = nums[begin];
dp[begin+1] = max(nums[begin+1], nums[begin]);
for(int i = begin+2; i <= end; i++){
dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[end];
}
int rob(vector<int>& nums) {
//房屋围成了一个圈,所以递推公式改变,需要标记第一个位置
//dp[i] = max(dp[i-1], dp[i-2]+nums[i])
if(nums.size()==1) return nums[0];
if(nums.size() == 0) return 0;
if(nums.size() == 2) return max(nums[0], nums[1]);
int sum1 = calRob(nums, 0, nums.size()-2);
int sum2= calRob(nums, 1, nums.size()-1);
if(sum1 > sum2) return sum1;
return sum2;
}
};
3. 打家劫舍Ⅰ
参考文档:代码随想录
分析:
dp五部曲:文章来源:https://www.toymoban.com/news/detail-836848.html
- dp[i]含义:考虑[0, i]的房子可以偷窃的最大金额。
- 递推公式:dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
- 初始化:dp[0] = nums[0], dp[1] = max(dp[0], dp[1]);
- 遍历顺序:从前到后更新。
代码:
class Solution {
public:
int rob(vector<int>& nums) {
//当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。
//dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
vector<int> dp(nums.size(),0);
if(nums.size() == 1) return nums[0];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[nums.size() -1];
}
};
到了这里,关于【Day52】代码随想录之动态规划_打家劫舍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!