首页 / 更多教程 / LeetCode—House Robber 寻找数组不相邻组合最大值DP

LeetCode—House Robber 寻找数组不相邻组合最大值DP

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode—House Robber 寻找数组不相邻组合最大值DP，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1389字，纯文字阅读大概需要2分钟。

内容图文

https://leetcode.com/problems/house-robber/

题目设计了一个抢劫犯的情景，其实就是求数组中不相邻数据进行组合得到的最大值

举一个例子

假设数据： 8 3 6 15 4 9 7 10

那么首先可能选取 8 ， 3

每一个数字的选取都是根据他的前两个数字，前三个数字得到的最大值进行选择，等到6的时候考虑前面只能和8组合  8，3,14

到数字15，那么就可以考虑在8,3中进行组合  8,3,14,23,4,9,7,10

接下来的步骤：

8,3,14,23,18,9,7,10

8,3,14,23,18,32,7,10

8,3,14,23,18,32,30,10

8,3,14,23,18,32,30,42  最后是42

class Solution {
public:
    int rob(vector<int> &num) {
        if(num.empty())
        {
            return 0;
        }
        int res = 0;
        int length = num.size();
        if(1 == length)
        {
            return num[0];
        }
        if(length >= 3)
        {
            num[2] = num[0]+num[2];
        }
        for(int i = 3; i < length; i++)
        {
            if(num[i-2]>num[i-3])
            {
                num[i] += num[i-2];
            }
            else
            {
                num[i] += num[i-3];
            }
            
        }
        return (num[length-2]>num[length-1])? num[length-2]:num[length-1];
        
    }
};


其实这是一个DP的问题：

A[i][0]表示第i次没有抢劫，A[i][1]表示第i次进行了抢劫

即A[i+1][0] = max(A[i][0], A[i][1])..  那么rob当前的house，只能等于上次没有rob的+money[i+1], 则A[i+1][1] = A[i][0]+money[i+1].

实际上只需要两个变量保存结果就可以了，不需要用二维数组

  1. class Solution {  
  2. public:  
  3.     int rob(vector<int> &num) {  
  4.         int best0 = 0;   // 表示没有选择当前houses  
  5.         int best1 = 0;   // 表示选择了当前houses  
  6.         for(int i = 0; i < num.size(); i++){  
  7.             int temp = best0;  
  8.             best0 = max(best0, best1); // 没有选择当前houses，那么它等于上次选择了或没选择的最大值  
  9.             best1 = temp + num[i]; // 选择了当前houses，值只能等于上次没选择的+当前houses的money  
  10.         }  
  11.         return max(best0, best1);  
  12.     }  
  13. };  


原文：http://blog.csdn.net/xietingcandice/article/details/45015119

内容总结

以上是互联网集市为您收集整理的LeetCode—House Robber 寻找数组不相邻组合最大值DP全部内容，希望文章能够帮你解决LeetCode—House Robber 寻找数组不相邻组合最大值DP所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1236568.html

来源：【匿名】