做网站如何把栏目放到首页,切片,lv官网手表,网络管理系统的基本组成和功能阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
此题使用动态规划求解#xff0c;假设 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 代表不偷窃第 i i i 个房屋可以获得的最高金额#xff0c;而 d p [ i ] [ 1 ] dp[i][1] dp[i][1] 代表偷窃第 i i i 个房屋可以获… 阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
此题使用动态规划求解假设 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 代表不偷窃第 i i i 个房屋可以获得的最高金额而 d p [ i ] [ 1 ] dp[i][1] dp[i][1] 代表偷窃第 i i i 个房屋可以获得的最高金额。那么转移方程为 d p [ i 1 ] [ 0 ] m a x ( d p [ i ] [ 0 ] , d p [ i ] [ 1 ] ) dp[i1][0] max(dp[i][0], dp[i][1]) dp[i1][0]max(dp[i][0],dp[i][1])
不偷窃第 i 1 i1 i1 个房屋时第 i i i 个房屋可以偷也可以不偷所以取二者的最大值。 d p [ i 1 ] [ 1 ] d p [ i ] [ 0 ] n u m s [ i 1 ] dp[i1][1] dp[i][0] nums[i1] dp[i1][1]dp[i][0]nums[i1]
要偷窃第 i 1 i1 i1 个房屋的话第 i i i 个房屋一定不可以偷所以取前一个房间不偷窃可以获得的最大金额再加上当前房屋的价值。
由于 d p [ i 1 ] dp[i1] dp[i1] 只和 d p [ i ] dp[i] dp[i] 有关系所以我们只需要两个状态值即可。
时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1).
3. 代码实现
class Solution {
public:int rob(vectorint nums) {int stole_value 0;int not_stole_value 0;int max_value 0;for (int i 0; i nums.size(); i) {int temp not_stole_value;not_stole_value max(stole_value, not_stole_value);stole_value temp nums[i];max_value max(max_value, stole_value);}return max_value;}
};
