你的浏览器还没开启 Javascript 功能!

算法题(五)打家劫舍

前言

鸽了蛮久的算法题分析系列,之前都写的是一些社科类文章,都快忘了网站里还有有技术文章标签,哈哈。嗝~

这道题是某位老铁一起来跟我一起探讨的,可以在leetcode上找到,属于动态规划系列,我们来看看。

快速审题

你是一个专业的小偷,计划偷窃沿街的房屋。每间房都藏有一定的现金,影响你偷窃的唯一制约因素就是两间相邻的房屋在同一晚上被偷窃,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报的情况下,能偷窃到的最高金额

示例1:

输入:[1,2,3,1]
输出:4
解释:偷窃1号房屋(金额 = 1),然后偷窃3号房屋(金额 = 3)。偷窃到最高金额 = 1 + 3 = 4。

示例2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃1号房屋(金额 = 2),然后偷窃3号房屋(金额 = 9),接着偷窃5号房屋(金额 = 1)。偷窃到最高金额 = 2 + 9 + 1 = 12。

冷静分析

仔细观察条件,关键点有:

  • 相邻不能偷窃
  • 得到最高金额

则对于金额数组,下标不能连续,那怎么判断选择能得到最高金额呢?

看看真实数据[2,7,9,3,1]

假设你已经拿到了下标0的金额2,这是下标来到了1,金额为7,很明显7>2,这时候我抛弃第0家,选择了第一家金额为7。

换一家,到了下标2,金额为9,啊?这难受啊,刚选择了7,明显9比7大啊,而且由于第0家和第2家不是相邻的,那我可以得到 2 + 9 = 11金额。血赚。换!

作为毛贼,有了思路后赶紧想到了规律:

到了第i家,得到最高金额 = max( 在上上家也就是i-2能得到的最高金额 + 当前第i家的金额, 在上家i-1能得到的最高金额 )

上面真实情况可以转化为公式,即:

dp[i] = max(dp[i-2] + A[i], dp[i-1])

哈哈~天下第一神偷,盗圣在此!

实现梦想

拿着公式的毛贼来到一处富宅区,早就蹲点打听到了每家的铜钱数,数量太大,单位就为万两吧。

const nums = [2,7,9,3,1];

啧啧~ 土豪啊,先制定一下任务

var task = (nums) => {
    // 如果没得偷,就换个地方吧,此处穷鬼~ 
    if(nums.length === 0) {
        return 0;
    }

    // 咦?第一个土豪家前面还有两家穷鬼房子
    var dp_prev_2 = 0;
    var dp_prev_1 = 0;
    // 现在口袋空空
    var dp_cur = 0;

    // 开始整活 
    for(var i = 0; i < nums.length; i++) {
        // 先看看这个土豪家有几百万两银子
        var cur = nums[i];
        // 掏出口袋的公式看看 看看怎么偷 价值最大
        dp_cur = Math.max(dp_prev_2 + cur, dp_prev_1);
        // 好的,更新一下数值
        dp_prev_2 = dp_prev_1;
        dp_prev_1 = dp_cur;
    }

    // 嘿嘿,不触发警报的情况下,最大利益已经计算出来啦
    console.log(dp_cur);
    return dp_cur;
}

“官差大人,您看!这就是小的当时的思路~,task([2,7,9,3,1]) = 12,可带劲了!”。