视频网站开发php,爆款采集推广引流软件,品牌网站建设 51下拉,怎样做免费网站的推广思路 1#xff1a; 我将res[i]定义为#xff1a;一定要取第 i 个房子的前提下#xff0c;能获取的最大金额。那么直接用cnt从头记录到尾#xff0c;每个房子的res最大值即是答案。那么递推公式是什么#xff1f;res[i]max(res[i-2],res[i-1],...,res[0])nums[i]。数组初始…
思路 1 我将res[i]定义为一定要取第 i 个房子的前提下能获取的最大金额。那么直接用cnt从头记录到尾每个房子的res最大值即是答案。那么递推公式是什么res[i]max(res[i-2],res[i-1],...,res[0])nums[i]。数组初始化是什么res[i]nums[i]也就是只取每个房子的金额。 代码
C
class Solution {
public:int rob(vectorint nums) {int lennums.size();int cnt0;vectorint res(len,0); //以该房子为结尾偷盗的最大金额//那如果res[i]定义为截止到房子i为止能获取的最大金额呢//初始化resfor(int i0;ilen;i){res[i]nums[i];cntmax(cnt,res[i]);}for(int i0;ilen;i){for(int j0;ji-2;j){res[i]max(res[i],res[j]nums[i]);cntmax(cnt,res[i]);}}return cnt;}
};
Python
class Solution:def rob(self, nums: List[int]) - int:len_numslen(nums)cnt0res[0]*len_numsfor i in range(len_nums):res[i]nums[i]cntmax(cnt,res[i])for i in range(len_nums):for j in range(i-1):res[i]max(res[i],res[j]nums[i])cntmax(cnt,res[i])return cnt
那如果res[i]定义为偷前 i 个房子能获取的最大金额呢递推公式是什么呢数组初始化又是什么呢
思路2 递推公式为g[i]max(g[i-1],g[i-2]nums[i]) 可以看一下标答还是很清晰的198. 打家劫舍 - 力扣LeetCode 数组初始化 要考虑len(nums)1的情况哦别掉进坑了 g[0]nums[0],g[1]max(nums[0],nums[1]) 代码
C
class Solution {
public:int rob(vectorint nums) {int lennums.size();if(len1){return nums[0];}vectorint g(len,0);g[0]nums[0];g[1]max(nums[0],nums[1]);for(int i2;ilen;i){g[i]max(g[i-1],g[i-2]nums[i]);}return g[len-1];}
};
Python
class Solution:def rob(self, nums: List[int]) - int:len_numslen(nums)if len_nums1:return nums[0]g[0]*len_numsg[0]nums[0]g[1]max(nums[0],nums[1])for i in range(2,len_nums):g[i]max(g[i-1],g[i-2]nums[i])return g[len_nums-1]
