xindoo is
always here

Leetcode 198. House Robber

原题链接:198. House Robber

  一句话理解题意,有个偷马贼晚上要偷尽可能值钱的马,但连续两头马被偷会触发报警,问他如何在不触发报警(不偷连续的两匹马)的情况下偷到总价值最高马,返回最高总价值。
  看到maximum,就应该想到这是应该求解最优的问题,一想到求解最优,一般除了暴力就是动态规划了。

  我们先来看看暴力解法,此题暴力还是比较复杂的,枚举每个位置的马偷或者不偷,用递归可以很简单的实现,然后再排除连续的情况。想想时间复杂度,已经到了惊人的O(2^n),一般n到20左右一般的计算机就抗不住了。

  如果是动态规划又会怎么样?如果robber在第i个位置,他如何保证在此位置获得最大的价值,他肯定有两种选择,偷或者不偷第i匹马。如果偷的情况下最大价值是啥?不偷又是啥?如果你想通了,你肯定会得到两种情况下的转态转移方程。偷第I批马 dp[1][i] = Math.max(dp[1][i-1], dp[0][i-1]+nums[i]),不偷 dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1])。 这里我用 0和1表示不偷和偷。
   本人Java代码如下:

public class Solution {
    public int rob(int[] nums) {
        if (0 == nums.length)
            return 0;
        int[][] dp = new int[2][nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (0 == i) {
                dp[0][0] = 0;
                dp[1][0] = nums[0];
            }
            else if (1 == i) {
                dp[0][1] = nums[0];
                dp[1][1] = nums[1];
            }
            else {
                dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
                dp[1][i] = Math.max(dp[1][i-1], dp[0][i-1]+nums[i]);
            }
        }
        return Math.max(dp[0][nums.length-1], dp[1][nums.length-1]); 
    }
}
打赏
未经允许不得转载:XINDOO » Leetcode 198. House Robber
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏