【学习】算法小记

简单 746 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算从底部到楼梯顶部的最低花费。

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//虽然基础，也是很有代表性的一道动态规划题。
//在爬楼梯的基础上加一层判断，即每一层的最小花费是上一层和上上层最小花费加上当层费用。
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] mincost = new int[cost.length+1];
        mincost[0] = 0;
        mincost[1] = 0;
        for(int i=2;i<cost.length+1;i++){
            mincost[i] = mincost[i-1]+cost[i-1]<mincost[i-2]+cost[i-2]?mincost[i-1]+cost[i-1]:mincost[i-2]+cost[i-2];
        }
        return mincost[cost.length];
    }
}
//使用这种解法需要记录每层的花费，但这是不必要的
//通过观察可知其实一层一层往后推，用到的只有最高三层的花费值
//那么只记录这三层的花费就行了呀，因此如下优化，空间复杂度优化为O（1）
//解法二：
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int last=0,prelast=0,curcost=0;
        for(int i=2;i<len+1;i++){
            curcost = Math.min(last+cost[i-1],prelast+cost[i-2]);
            prelast = last;
            last = curcost;
        }
        return curcost;
    }
}

中等 198 打家劫舍

你是一个专业的小偷（我不是），计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//经典的动态规划，要用爬楼梯的逆向思维来解。
//这题做的时候有点钻牛角尖
//一开始我想的是，记录最后两个状态的最大值，然后返回更大的一个
//这样想没问题但完全没必要，写出的题解十分拖沓，下面是乱七八糟的题解：
class Solution {
    public int rob(int[] nums) {
        if(nums.length==1)return nums[0];
        if(nums.length==2)return Math.max(nums[0],nums[1]);
        if(nums.length==3)return Math.max(nums[1],nums[0]+nums[2]);
        int q1=nums[0],q2=nums[1],q3=nums[0]+nums[2],q4=Math.max(q1,q2)+nums[3];
        for(int i=4;i<nums.length;i++){
            q1 = q2;
            q2 = q3;
            q3 = q4;
            q4 = Math.max(q1,q2)+nums[i];
        }
        return Math.max(q3,q4);
    }
}

//好，虽然pass了，但用了4个变量，非常难看。
//其实只需要记录：1.选上一家打劫，那本家就不能计算入内；2.不选上一家打劫，选择上上家和本家打劫
//然后比较，选出最大值，这样就好看多了：
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len==1)return nums[0];
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2;i<len;i++){
            dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[len-1];
    }
}