【代码随想录】【算法训练营】【第45天】 [198]打家劫舍 [213]打家劫舍II [337]打家劫舍III

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 45，周五，坚持不了一点~

题目详情

[198] 打家劫舍

题目描述

198 打家劫舍

解题思路

前提：相邻两房屋不能连续盗窃
思路：动态规划, dp[i]: [0, i]的房屋中最多可以偷窃的金额，考虑偷窃第i房dp[i - 2] + nums[i]，和不偷窃第i房dp[i - 1]，取两者较大值
重点：dp数组推导公式、初始化

代码实现

C语言

动态规划

// 动态规划, dp[i]: [0, i]的房屋中最多可以偷窃的金额
// dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}int rob(int* nums, int numsSize) {if (numsSize == 0) {return 0;}if (numsSize == 1) {return nums[0];}int dp[numsSize];// dp数组初始化dp[0] = nums[0];dp[1] = maxFun(nums[0], nums[1]);for (int i = 2; i < numsSize; i++) {dp[i] = maxFun(dp[i - 1], dp[i - 2] + nums[i]);}return dp[numsSize - 1];
}

[213] 打家劫舍II

题目描述

213 打家劫舍II

解题思路

前提：相邻两房屋不能连续盗窃，且首尾不能同时盗窃
思路：动态规划, 首尾不能同时盗窃，分别去除首尾考虑两种情况，取最大值；对于每个情况，dp[i]: [0, i]的房屋中最多可以偷窃的金额，考虑偷窃第i房dp[i - 2] + nums[i]，和不偷窃第i房dp[i - 1]，取两者较大值
重点：dp数组推导公式、初始化

代码实现

C语言

动态规划

// 动态规划, 分为两种情况, 取较大值
// 情况一: 不考虑最后一个房屋, dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
// 情况二: 不考虑第一个房屋, dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}int rangeFun(int *nums, int start, int end)
{if (start == end) {return nums[start];}int dp[end - start + 1];// dp数组初始化dp[0] = nums[start];dp[1] = maxFun(nums[start], nums[start + 1]);for (int i = 2; i <= end - start; i++) {dp[i] = maxFun(dp[i - 1], dp[i - 2] + nums[start + i]);}return dp[end - start];
}int rob(int* nums, int numsSize) {if (numsSize == 0) {return 0;}if (numsSize == 1) {return nums[0];}int result1 = rangeFun(nums, 0, numsSize - 2);int result2 = rangeFun(nums, 1, numsSize - 1);return maxFun(result1, result2);
}

[337] 打家劫舍III

题目描述

337 打家劫舍III

解题思路

前提：树上相连的两房屋不能连续盗窃
思路：树形dp, 递归 + 动态规划，后序遍历，考虑两种情况，情况一: 考虑偷该结点, 该子节点均不能偷，情况二: 不考虑偷该结点，该子节点可以考虑偷，此时子节点可偷可不偷，取两者较大值
重点：递归 + 动态规划，推导公式

代码实现

C语言

树形dp

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 树形dp, 递归 + 动态规划
// 后序遍历 考虑两种情况
// 情况一: 考虑偷该结点, 该子节点均不能偷
// 情况二: 不考虑偷该结点，该子节点可以考虑偷int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}void traversal(struct TreeNode *root, int *dp)
{// 退出条件if (root == NULL) {dp[0] = 0;dp[1] = 0;return ;}// 后序遍历, 左右中int leftDp[2];int rightDp[2];// 初始化dp数组for (int i = 0; i < 2; i++) {leftDp[i] = 0;rightDp[i] = 0;}if (root->left) {traversal(root->left, leftDp);}if (root->right) {traversal(root->right, rightDp);}// 情况一: 考虑偷该结点, 该子节点均不能偷dp[1] = root->val + leftDp[0] + rightDp[0];// 情况二: 不考虑偷该结点，该子节点可以考虑偷dp[0] = maxFun(leftDp[0], leftDp[1]) + maxFun(rightDp[0], rightDp[1]);return ;
}int rob(struct TreeNode* root) {// 0 - 考虑不偷该结点, 1 - 考虑偷该结点int dp[2];// 后序遍历traversal(root, dp);return maxFun(dp[0], dp[1]);
}