剑指offer专项突击版第30天

剑指 Offer II 088. 爬楼梯的最少成本

dp方程 $cost[i]+=min(cost[i-1],cost[i-2])$ ，其中 $cost[i]$ 当前阶梯到下个阶梯所需要消耗的最小值，$min(cost[i-1],cost[i-2])$ 为上个阶梯到当前阶梯所要消耗的最小值。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        cost.push_back(0);
        for(int i = 2; i < cost.size(); i++) {
            cost[i] += min(cost[i-1],cost[i-2]);
        }
        return cost.back();
    }
};
1
2
3
4
5
6
7
8
9
10

---

剑指 Offer II 089. 房屋偷盗

朴素 $DP$ 做法，在第 $i-2$，$i-3$ 之中取最大值。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0],nums[1]);

        nums[2] += nums[0];
        //因为跨度有4个，为了防止漏掉 nums[2] + nums[0]
        int res = max(nums[2],nums[1]); 
        for(int i = 3; i < nums.size(); i++) {
            nums[i] += max(nums[i-2], nums[i-3]);
            res = max(nums[i],res);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路基于朴素 $DP$，使用记忆化搜索实现，更好理解

class Solution {
public:
    vector<int> dp;
    int rob(vector<int>& nums) {
       int n = nums.size();
       dp.resize(n,-1);
       return max(dfs(n-2,nums),dfs(n-1,nums));
    }  

    int dfs(int pos, vector<int> &nums) {
        if(pos < 0) return 0;
        if(dp[pos] != -1) return dp[pos]; //如果搜索过了就直接回溯
        dp[pos] = nums[pos] + max(dfs(pos-2,nums),dfs(pos-3,nums));
        return dp[pos];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

更简洁的 $DP$ 写法，$dp[i]$ 表示 盗取 $nums[i]$ 之前可以获得的最大价值。

class Solution {
public:
   int rob(vector<int>& nums) {
        int dp[nums.size()+2];
        memset(dp,0,sizeof(dp));
        for(int i=2;i<=nums.size()+1;i++)
            dp[i] = max(dp[i-2]+nums[i-2],dp[i-1]);
        return dp[nums.size()+1];
    }
};
1
2
3
4
5
6
7
8
9
10

---

剑指 Offer II 090. 环形房屋偷盗

环形房屋主要就是避免头尾同时选，那么就分两种情况：1、不考虑尾 2、不考虑头。
在这两种情况的最优值中取一个最大即可。

class Solution {
public:
    int robRange(vector<int> &nums, int st, int ed) {
        int dp[2]={nums[st],max(nums[st],nums[st+1])};
        for(int i = st+2; i < ed; i++) {
            int t = dp[1];
            dp[1] = max(dp[0]+nums[i], dp[1]);
            dp[0] = t;
        }
        return dp[1];
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        if(n==2) return max(nums[0],nums[1]);
        return max(robRange(nums,0,n-1),robRange(nums,1,n));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18