成品软件源码网站大全,注册公司100万意味着什么,西安小程序专业开发公司,网站搭建维护淄博198. 打家劫舍
题目分析
动态规划数组初始化#xff1a;
dp[0]被初始化为0#xff0c;因为没有房屋可以盗窃时的最大金额为0。dp[1]被初始化为nums[0]#xff0c;意味着如果只有一家房屋#xff0c;盗贼将盗取这家的金额。dp[2]被初始化为std::max(nums[0], nums[1])
dp[0]被初始化为0因为没有房屋可以盗窃时的最大金额为0。dp[1]被初始化为nums[0]意味着如果只有一家房屋盗贼将盗取这家的金额。dp[2]被初始化为std::max(nums[0], nums[1])这表示如果有两家房屋盗贼将选择金额较大的那家进行盗窃。
动态规划解法
循环从i 3开始因为前两个情况即dp[1]和dp[2]已经被手动设定。对于dp数组中的每个后续位置i都通过比较不盗窃当前房屋即dp[i - 1]的值和盗窃当前房屋即dp[i - 2] nums[i - 1]的值之间的较大值来进行更新。这反映了一个事实盗窃当前房屋意味着必须跳过前一个房屋而不盗窃则保留前一个房屋的决策结果。循环结束后通过dp数组可以看出从第一家到每家房屋盗窃的最大金额。
输出和返回结果
打印出dp数组的内容这有助于验证和理解动态规划的逐步解答过程。返回dp[nums.size()]作为最终结果表示考虑所有房屋时可以盗窃的最大金额。
acm模式代码
#include iostream
#include vectorclass Solution {
public:int rob(std::vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];std::vectorint dp(nums.size() 1, 0);dp[1] nums[0];dp[2] std::max(nums[0],nums[1] );for (int i 3; i nums.size(); i) {dp[i] std::max(dp[i - 2] nums[i - 1], dp[i - 1]);}// for (int i : dp) {// std::cout i ;// }return dp[nums.size()];}
};int main() {Solution sol;std::vectorint nums {2, 7, 9 ,3 ,1};int res sol.rob(nums);std::cout std::endl;std::cout res: res std::endl;return 0;
}
213 打家劫舍2
. - 力扣LeetCode
题目分析
在这个变种中房屋排列成一个圈这意味着第一家和最后一家是相邻的盗贼不能同时从这两家盗窃。因此问题变成了两个子问题
不考虑最后一家房屋即只考虑从第一家到倒数第二家的房屋。不考虑第一家房屋即只考虑从第二家到最后一家的房屋。
对这两个子问题分别使用“打家劫舍”问题的解决方案然后取这两个解的最大值作为最终答案。
robliner方法
robliner方法实现了原始的“打家劫舍”问题的解决方案用于处理一排线性排列的房屋即没有首尾相连。它首先处理一些基本情况
如果没有房屋则返回0。如果只有一家房屋则返回这家的金额。
然后它初始化一个动态规划数组dp其中dp[i]表示到达第i个位置时能够盗取的最大金额。通过动态规划的方法填充这个数组并返回最大可能的盗窃金额。
rob方法
rob方法解决了房屋排列成圈的问题。它首先创建了两个子数组nums1和nums2
nums1包含从第一家到倒数第二家的所有房屋即不考虑最后一家。nums2包含从第二家到最后一家的所有房屋即不考虑第一家。
接着它对这两个子数组分别调用robliner方法来解决线性排列的“打家劫舍”问题并取这两个结果的最大值作为最终答案。
总结
这种方法巧妙地将圈形排列的房屋问题转化为了两个线性排列的房屋问题并复用了原始“打家劫舍”问题的解决方案。这样不仅提高了代码的复用性也简化了问题的解决流程。最终通过比较两种情况下的最大盗窃金额来得到全局的最大值。
acm代码
#include iostream
#include vectorclass Solution {
public:int robliner(std::vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];std::vectorint dp(nums.size() 1, 0);dp[1] nums[0];dp[2] std::max(nums[0],nums[1] );for (int i 3; i nums.size(); i) {dp[i] std::max(dp[i - 2] nums[i - 1], dp[i - 1]);}// for (int i : dp) {// std::cout i ;// }// std::cout std::endl;return dp[nums.size()];}int rob(std::vectorint nums) {std::vectorint nums1(nums.begin(), nums.end() - 1);std::vectorint nums2(nums.begin() 1, nums.end());int res std::max(robliner(nums1), robliner(nums2));return res;}
};int main() {Solution sol;std::vectorint nums {1, 2 ,3 ,1};int res sol.rob(nums);std::cout std::endl;std::cout res: res std::endl;return 0;
}
337. 打家劫舍 III
题目分析 robtree 方法这是一个递归函数用于计算从当前节点开始可以偷窃的最大金额。 如果当前节点为nullptr返回两个0表示没有可偷窃的金额。否则递归调用robtree方法计算左右子节点的最大偷窃金额。因为left和right是std::unique_ptr所以使用.get()方法来获取它们所管理的裸指针以符合robtree函数的参数要求。计算当前节点偷窃(dp[0])和不偷窃(dp[1])的情况下的最大金额然后返回这两个值。 rob 方法接收树的根节点的裸指针调用robtree方法并返回从根节点开始可以偷窃的最大金额。
acm模式代码
#include iostream
#include vector
#include memorystruct TreeNode
{int val;// TreeNode *left;// TreeNode *right;std::unique_ptrTreeNode left;std::unique_ptrTreeNode right;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:std::vectorint robtree(TreeNode* cur) {//下标为0,偷当前节点下标为1,不偷当前节点std::vectorint dp {0,0};if (cur nullptr) return {0, 0};std::vectorint leftdp robtree(cur-left.get());// 使用.get()访问原始指针std::vectorint rightdp robtree(cur-right.get());//偷dp[0] cur-val leftdp[1] rightdp[1];//不偷dp[1] std::max(leftdp[0], leftdp[1]) std::max(rightdp[0], rightdp[1]);return dp;}int rob(TreeNode* root) {std::vectorint result robtree(root);return std::max(result[0], result[1]);}
};int main() {// 使用 unique_ptr 构建树std::unique_ptrTreeNode root std::make_uniqueTreeNode(3);root-left std::make_uniqueTreeNode(2);root-right std::make_uniqueTreeNode(3);root-left-right std::make_uniqueTreeNode(3);root-right-right std::make_uniqueTreeNode(1);Solution solution;std::cout Maximum amount of money the thief can rob: solution.rob(root.get()) std::endl;// 无需手动释放内存return 0;
}// int main() {
// // 构建一个示例树 3
// // / \
// // 2 3
// // \ \
// // 3 1
// TreeNode* root new TreeNode(3);
// root-left new TreeNode(2);
// root-right new TreeNode(3);
// root-left-right new TreeNode(3);
// root-right-right new TreeNode(1);// Solution solution;
// std::cout Maximum amount of money the thief can rob: solution.rob(root) std::endl;// // 删除分配的内存
// delete root-left-right;
// delete root-right-right;
// delete root-left;
// delete root-right;
// delete root;// return 0;
// }
