Loading...
墨滴

Shinkai005

2021/12/13  阅读:37  主题:红绯

【leetcode】198.打家劫舍

【leetcode】198.打家劫舍

题目描述

image-20211212225350641
image-20211212225350641

题目思路

F(k) 从前K个房屋中能偷窃到的最大数额

Ak = 第K个房屋的钱

F(k) = max(f(k-2)+Ak,f(k-1));

个人题解

/**
 * @param {number[]} nums
 * @return {number}
 */

var rob = function (nums{
    /**
     定义子问题: f(k) = max(f(k-2)+Ak,f(k-1))
     反复执行:从2循环到n,执行上述公式
     */

    if (nums.length === 0) {
        return 0;
    }
    const dp = [0, nums[0]];//用来记录过去能打劫到的最大金额
    for (let i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    return dp[dp.length - 1];

};

详细记录下这代码是怎么写出来的

保姆教程..仅此一次

  1. 最先应该是先确定使用动态规划的思想,这个其实很好发现, 因为你之后的金钱总量肯定是有一部分是之前的,也就是有==重合部分==,因此是动态规划.
  2. 接下来那段数学公式是必须得出来的.[2,8,9,5,1]
    1. 算了解释下如何得出这段公式
    2. 先看题目中的两个例子[1,2,3,1] [2,7,9,3,1]
    3. 第一个例子,自己脑海中遍历思考最优解, 1+3 = 4 , 2+1=3
    4. 第二个例子,一样,2+9+1 = 12 7+3 =10;
    5. 这个时候思考一下, 如果后面相加更大呢? 自己加新的例子
    6. [1,4,3,1] 1+3=4 4+1=5; [2,8,9,5,1] 2+9+1 =12 8+5=13
    7. 再找一个例子,有没有隔离俩的情况? [2,1,9,12,1] 2+12=14 2+9+1 =12 1+12=13
  3. 这样是不是就知道了,其实是在不停地找前2个最优解,前3个最优解,前4个最优解,依次到前N个最优解?
  4. 接下来看具体公式, [2,8,9,5,1]
    1. 当找前两个最优时,第0个数和第2个数和 与 第1个数比 是8
    2. 当找前3个最优时, 第一个数和第三个数和 与第二个数比 是11
    3. 当找前四(k)个最优时, 比较8+5 和 2+9 也就是 k-2 + 当前k的值 和 k-1哪一个大?
    4. 得出F(k) = max(f(k-2)+Ak,f(k-1));

看不懂我没办法了!!!,我很努力了

接下来的代码其实是通用的,都是一个套路

(0的判断可有可无不影响,只是一般会判断一下传值,好习惯,这道题确实可以删除哦)

dp // data processing 数据处理

用dp来存前两次的值,为了之后的叠加

最后在记录返回值

三步骤

  1. dp 来存初始值 // 注意点,0是否存在
  2. for循环 写公式 // 注意点,是否会取到负值等,带极端值进去检验
  3. 返回值 //极端值没办法返回就写一个判断直接返回就好

总结优化

这个优化也是套路, 只有当不需要记录中间过程的时候可以这样做. // 如果问你前10个又问你前5个这个时候如果用数组就可以直接回答.

  1. 两个变量来记录初始值,
  2. 在循环中声明一个临时变量来记录 新值 ,剩下变量往前移动一位, dp1赋值给dp0 新的temp赋值给dp1;
  3. 返回dp1
/**
 * @param {number[]} nums
 * @return {number}
 */

var rob = function (nums{
    /**
     定义子问题: f(k) = max(f(k-2)+Ak,f(k-1))
     反复执行:从2循环到n,执行上述公式
     */

    if (nums.length === 0) {
        return 0;
    }
    let dp0 = 0;
    let dp1 = nums[0];
    for (let i = 2; i <= nums.length; i++) {
        const temp = Math.max(dp0 + nums[i - 1], dp1);
        dp0 = dp1;
        dp1 = temp;
    }
    return dp1;

};

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

O(n)优化后是

O(1)

Shinkai005

2021/12/13  阅读:37  主题:红绯

作者介绍

Shinkai005