[算法]震惊!竟有人这样进行偷窃(动态规划)

发表于 算法 2017-04-15 阅读数: 201

假如你是一个偷窃犯,你想要在半夜偷华狮街上的房子内的金钱,每个房子内都有一定量的金额,但是如果你偷了连续相邻的两个房子,便会惊扰警察。现在给定你N个房子,请问你要怎么偷窃才能在不惊扰警察的情况下得到最多的金钱呢?

比如现在有十间房子,里面含有的金钱分别是:5,6,3,7,6,12,18,2,6,10 . 请问你怎么样才能偷得最多的钱呢?

答案是42。5+3+6+18+10 = 42,这个答案并不是那么好想,尤其是当N变得特别大的时候则更难想得到了。这时候我们就要思考怎么样让计算机帮我们进行计算。

实际上问题的解法可以从下面这两种情况得到:

1. 倘若我们偷了上一个房子的钱,那么我们就无法偷当前房子的钱,最大收益就是到上个房子为止。

2. 倘若我们偷了这个房子的钱,那么总收益就是这个房子加偷到上上个房子为止的钱的总额。

从这里我们可以得到一种递归的解决方法:

int rob(std::vector<int> &nums){

    int n = nums.size();

    if(n == 1)

        return nums[0];

    if(n == 2)

        return std::max(nums[0], nums[1]);

    std::vector<int> temp1 = std::vector<int>(nums.begin()+1,nums.end());

    std::vector<int> temp2 = std::vector<int>(nums.begin()+2,nums.end());

    return std::max(rob(temp1),rob(temp2)+nums[0]);

}

比如说 [2,6,10],temp1得到 [6,10] 这个数组,因此rob(temp1)会得到 [10],rob(temp2)得到 [10]. 然后比较10+2和10的大小,最终取得12。现在我们再加个数:[18,2,6,10] temp1会变成[2,6,10],temp2会变成[6,10],我们可以看出temp1是上一次的结果,答案为12(不加当前房子,情形1),temp2则是上一次结果中的子结果,答案为10,显然10+18 = 28 >12(情形2),因此结果又发生了变化,如此类推。

递归固然好,但是费时间!我们可以看见,每次计算都运用了之前计算过的结果,那么我们是否可以利用这些结果,并且不用递归实现呢?这就是动态规划:

int rob(std::vector<int> &nums){

    if(nums.size() <= 1){

        return nums.size() == 0 ? 0 : nums[0];

    }    

    int a = nums[0];

    //a是上次的最大收益。

    int b = std::max(nums[0],nums[1]);

    //b是当前最大收益

    for(int i = 2; i < nums.size();++i){

        int temp = b;

        b = std::max(a+nums[i], b);

        //使b成为当前的最大收益(情形1或情形2)

        a = temp;

        //使a成为下一次计算的"上次的最大收益"

    }

    return b;

}

如此,希望这个算法能使你发家致富。

欢迎关注微信公众号:幻象客https://www.huanxiangke.com

欢迎进入极致分享:https://alltoshare.com

幻象客 二维码

Add comment