【动态规划专题】LeetCode 198. 打家劫舍

共以下 7 个回答

• kfaebot 普通 2024年5月11日 下午2:42

  class Solution {
  public:
      int rob(vector<int>& nums) {
          vector<int>dp(nums.size(),0);
  
          if(nums.size()==1){
              return nums[0];
          }
  
          //初始化
          dp[0]=nums[0];
          dp[1]=max(nums[0],nums[1]);
  
  
          //状态转移方程
          for(int i=2;i<nums.size();i++){
              dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
          }
          return dp[nums.size()-1];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Jimmy 普通 2024年4月14日 下午5:24

  子问题： dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);

  class Solution {
  public:
      int rob(vector<int>& nums) {
          if(nums.size() == 0)
          {
              return 0;
          }
          int N = nums.size();
          vector<int> dp(N+1,0);
          dp[0] = 0;
          dp[1] = nums[0];
          for(int i=2;i<=N;i++)
          {
              dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
          }
          return dp[N];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• heathhou 普通 2024年4月13日 下午3:17

  class Solution {
  public:
      int rob(vector<int>& nums) {
          if(nums.size() <= 0){
              return 0;
          }
          // 定义数组元素的含义
          // dp[k]: 偷前k间房子的最大金额
          vector<int> dp(nums.size()+1, 0);
  
          // 找出数组元素之间的关系式
          // dp[n] = max(dp[n-1], dp[n-2] + nums[n-1])
  
          // 找出初始值
          dp[0] = 0;
          dp[1] = nums[0];
  
          for(int k = 2; k <= nums.size(); ++k){
              dp[k] = max(dp[k-1], dp[k-2] + nums[k-1]);
          }
  
          return dp[nums.size()];
  
  
  
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 王位詮釋 普通 2024年4月8日 下午9:26

  class Solution {
      public int rob(int[] nums) {
          int length = nums.length;
          if(length<=0){
              return 0;
          }
          if(length==1){
              return nums[0];
          }
          if(length==2){
              return Math.max(nums[0],nums[1]);
          }
          //dp[i]表示到第i家的时候可以偷到的最大金额
          int[] dp = new int[length];
          //初始化
          dp[0] = nums[0];
          dp[1] = Math.max(nums[0],nums[1]);
          for(int i=2;i<length;i++){
              dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
          }
          return dp[length-1];
      }
  }
  思路：dp[i]表示到第i家的时候可以获得的最大金额，由于不能连续拿两家的钱，所以
  状态转移方程是：
  dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])；
  初始值dp[0] = nums[0]，dp[1] = Math.max(nums[0],nums[1])
  时间复杂度：O(n)
  空间复杂度：O(n)
  优化之后的：
  class Solution {
      public int rob(int[] nums) {
          int length = nums.length;
          if(length<=0){
              return 0;
          }
          if(length==1){
              return nums[0];
          }
          if(length==2){
              return Math.max(nums[0],nums[1]);
          }
          int res = 0;
          int odd = nums[0];
          int even = Math.max(nums[0],nums[1]);
          for(int i = 2;i<length;i++){
              res = Math.max(odd+nums[i],even);
              odd = even;
              even = res;
          }
          return res;
      }
  }
  时间复杂度为：O(n)
  空间复杂度为：O(1)
  

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月6日 下午3:29

  class Solution {
      public int rob(int[] nums) {
  
          if(nums.length<=1){
              return nums[0];
          }
          if(nums.length<=2){
              return Math.max(nums[0], nums[1]);
          }
          int []dp = new int [nums.length];
          dp[0]=nums[0];
          dp[1]=nums[0]>nums[1]?nums[0]:nums[1];
  
          // dp[2]=dp[0]+nums[2];
  
          //dp[i]的含义：准备离开第i家前，最多可能拥有的钱数
  
          int i;
          int j;
          int max;
          for(i=2;i<nums.length;i++){
              // max=0;
              // for(j=i-2;j>=0;j--){
              //     if(dp[j]>max); max=j;
              // }
              // dp[i]=max+nums[i];
              if((dp[i-2]+nums[i])>=dp[i-1]){
                  dp[i]=dp[i-2]+nums[i];
              }else{
                  dp[i]=dp[i-1];
              }
          }
  
  
  
          return dp[nums.length-1];
          // int dan=1;
          // int shuang=0;
          // int sum_dan=0;
          // int sum_shuang=0;
  
          // for(dan=1;dan<nums.length;){
          //     sum_dan+=nums[dan];
          //     dan=dan+2;
          // }
  
          // for(shuang=0;shuang<nums.length;){
          //     sum_shuang+=nums[shuang];
          //     shuang=shuang+2;
          // }
  
          // if(sum_dan>=sum_shuang){
          //     return sum_dan;
          // }else{
          //     return sum_shuang;
          // }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月4日 下午11:32

  class Solution {
  public int rob(int[] nums) {
  if(nums.length 1)
  return nums[0];
  int[] dp = new int[nums.length + 1];
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0],nums[1]);
  for(int i = 2; i < nums.length; i++){
  dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1]);
  }
  return dp[nums.length-1];

  }
  

  }
  //时空复杂度均为ON、

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月3日 下午9:25

  思路：假定数组 dp[i] 表示从房间 0 … i 可获得的最大价值，则 i 房间的东西有两种选择，偷或者不偷: dp[i] = max(dp[i-1], dp[i-2]+nums[i])

  “`c++
  class Solution {
  public:
  int rob(vector& nums) {
  int n = nums.size();
  if (n == 1) return nums[0];
  vector dp(n, 0);
  dp[0] = nums[0];
  dp[1] = max(dp[0], nums[1]);
  for (int i=2; i

  0 赞同 0 条回复

  登录以回复