第198题 House Robber

作者: 周伟林 分类: Leetcode 发布时间: 2018-05-02 11:51

题目描述

从一个数组中选择若干个数,选择的数字不能相邻,并且让这些数相加最大。返回这些数之和。

解题思路

寻找问题的子问题,包括递推公式和边界条件。

边界条件:f(0) = nums[0], f(1)=Math.max(nums[0], nums[1]);
递推公式:f(n) = Math.max(nums[n]+f(n-2), f(n-1))

例子

nums 6 4 2 4 6 8 9 4 2 5
dp 6 6 8 10 14 18 23 23 25 28

解法一, 暴力搜索,时间复杂度为2n

var rob1 = function(nums) {
    function solve(idx, nums){
        if(idx < 0) return 0;
        return Math.max(nums[idx]+solve(idx-2, nums), solve(idx-1, nums));
    }
    return solve(nums.length-1, nums);
};

解法二,计划搜索/备忘录(从后向前递归)

var rob2 = function(nums) {
    function solve(idx, nums){
        if(idx < 0) return 0;
        if(idx < dp.length) return dp[idx];
        dp.push(Math.max(nums[idx]+solve(idx-2, nums), solve(idx-1, nums)));
        // console.log(dp);
        return dp[idx];
    }
    let dp = [];
    return solve(nums.length-1, nums);
};

解法三,计划搜索/备忘录(非递归) — 推荐!

var rob3 = function(nums) {
    if(nums.length === 0) return 0;
    if(nums.length === 1) return nums[0];
    if(nums.length === 2) return Math.max(nums[0], nums[1]);
    let dp = [nums[0], Math.max(nums[0], nums[1])];
    for(let i = 2; i < nums.length; ++i){
        dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]);
    }
    return dp[nums.length-1];
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注