安全网站建设公司,怎么制作网站图片不显示,wordpress主题 问卷填报,中国建设银行官网站诚聘英才leetcode原题链接#xff1a;打家劫舍
题目描述 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系… leetcode原题链接打家劫舍
题目描述 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 1
输入[1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。
示例 2
输入[2,7,9,3,1]
输出12
解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12 。提示
1 nums.length 1000 nums[i] 400
解题方法动态规划。
1. 问题定义dp[k]表示nums[0...k]的最高偷窃金额
2. 初始化 dp[0] nums[0]; dp[1] std::max(nums[0], nums[1]);
3. 状态转移方程 dp[k] std::max(dp[k - 1], dp[k - 2] nums[k]);
4. 结果返回 dp[n - 1]
C代码
#include iostream
#include vector
class Solution {
public:int rob(std::vectorint nums) {int n nums.size();if (n 1) {return nums[0];}// 1. 问题定义dp[k]表示nums[0...k]的最高偷窃金额std::vectorint dp(n, 0);// 2. 初始化dp[0] nums[0];dp[1] std::max(nums[0], nums[1]);// 3. 从小到大求解,递归表达式: dp[k]std::max(dp[k-1], dp[k-2]num[k])for (int k 2; k n; k) {dp[k] std::max(dp[k - 1], dp[k - 2] nums[k]);}// 4. 返回结果return dp[n - 1];}
};
