LeetCode[动态规划] - #198 House Robber

原题链接：#198 House Robber

?

要求：

原题是要为某盗贼设计一个能使其利益最大化的方案（这个场景并不和谐，在保持题意的情况下重新描述一个场景）。假设某糖果工厂有若干糖果机，每台糖果机每天产出不同数量的糖果，每天取糖果时不能同时取相邻两台糖果机的糖果（别问为什么），问每天能取得的最大糖果数量是多少。

?

糖果机产生的糖果数量集合可以看成一个整型数组。

?

难度：简单

?

分析：

考虑使用动态规划来解决此问题。当糖果机只有1台时，取走这台产出的所有糖果；当糖果机有两台时，取走产出较多的糖果。当糖果机有三台时，有两种取法，取走第二台的产出的糖果，或取出第一台与第三台的所有糖果。假设第n台糖果机产出的糖果数量为S(n), 取到第n台为止时取到的最大糖果总数量为M(n)，则有：

M(1) = S(1)

M(2) = Max(S(1), S(2))

M(3) = Max(M(1)+S(3), M(2))

...

M(n) = Max(M(n-2)+S(n), M(n-1))

即是说，当取到第n台时，有两种方案，要么n-1台不取，此时糖果数量为前n-2台所取数量加上第n台的产出数量；要么第n台本身不取，保留前n-1台所取的总数量。在这两种方案中选取所取总数量较大者即可。

?

解决方案：

Java - 296 ms

public int rob(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        int[] maxMoney = new int[nums.length+1];
        maxMoney[nums.length] = 0;
        maxMoney[nums.length-1] = nums[nums.length-1];
        for(int i=nums.length-2; i>=0; i--){
            maxMoney[i]=(nums[i]+maxMoney[i+2]>maxMoney[i+1])?(nums[i]+maxMoney[i+2]):maxMoney[i+1];
        }
        return maxMoney[0];
    }

?简单测试程序

? ??

?

LeetCode[动态规划] - #198 House Robber

原文：http://cwind.iteye.com/blog/2232467