一、打家劫舍(一)

解法:动态规划

或许有人认为利用贪心思想，偷取最多人家的钱就可以了，要么偶数家要么奇数家全部的钱，但是有时候会为了偷取更多的钱，或许可能会连续放弃两家不偷，因此这种方案行不通，我们依旧考虑动态规划。

• 用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
• 如果数组长度为1，只有一家人，肯定是把这家人偷了，收益最大，因此dp[1]=nums[0]
• 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的i在dp中为数组长度，在nums中为下标。
  

class Solution {
public:
    int rob(vector<int>& nums) {
        //dp[i]表示长度为i的数组，最多能偷取多少钱
        vector<int> dp(nums.size() + 1, 0); 
        //长度为1只能偷第一家
        dp[1] = nums[0]; 
        for(int i = 2; i <= nums.size(); i++)
            //对于每家可以选择偷或者不偷
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        return dp[nums.size()];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n)，其中n为数组长度，遍历一次数组
空间复杂度：O(n)，动态规划辅助数组的空间

二、打家劫舍(二)

解法:动态规划

• 使用原先的方案是：用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。

• 如果数组长度为1，只有一家人，肯定是把这家人偷了，收益最大，因此dp[1]=nums[0]

• 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的i在dp中为数组长度，在nums中为下标。

• 此时第一家与最后一家不能同时取到，那么我们可以分成两种情况讨论：

情况1：偷第一家的钱，不偷最后一家的钱。初始状态与状态转移不变，只是遍历的时候数组最后一位不去遍历。
情况2：偷最后一家的请，不偷第一家的钱。初始状态就设定了dp[1]=0，第一家就不要了，然后遍历的时候也会遍历到数组最后一位。

• 最后取两种情况的较大值即可。

class Solution {
public:
    int rob(vector<int>& nums) {
        //dp[i]表示长度为i的数组，最多能偷取多少钱
        vector<int> dp(nums.size() + 1, 0); 
        //选择偷了第一家
        dp[1] = nums[0]; 
        //最后一家不能偷
        for(int i = 2; i < nums.size(); i++) 
            //对于每家可以选择偷或者不偷
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        int res = dp[nums.size() - 1]; 
        //清除dp数组，第二次循环
        dp.clear(); 
        //不偷第一家
        dp[1] = 0; 
        //可以偷最后一家
        for(int i = 2; i <= nums.size(); i++) 
            //对于每家可以选择偷或者不偷
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        //选择最大值
        return max(res, dp[nums.size()]); 
    }
};

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

C#使用动态规划解决0-1背包问题实例分析

pdf 0星 超过10%的资源 35KB

下载

时间复杂度：O(n)，其中n为数组长度，单独遍历两次数组
空间复杂度：O(n)，动态规划辅助数组的空间

三、买卖股票的最好时机(一)

解法一:动态规划(推荐)

• 用dp[i][0]表示第i天不持股到该天为止的最大收益，dp[i][1]表示第i天持股，到该天为止的最大收益。
• 第一天不持股，则总收益为0，dp[0][0]=0；第一天持股，则总收益为买股票的花费，此时为负数，dp[0][1]=−prices[0]
• 对于之后的每一天，如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天才卖掉，我们选择较大的状态dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])；
• 如果当天持股，有可能是前面若干天中买了股票，当天还没卖，因此收益与前一天相同，也有可能是当天买入，此时收益为负的股价，同样是选取最大值：dp[i][1]=max(dp[i−1][1]−prices[i])。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        vector<vector<int> > dp(n, vector<int>(2, 0)); 
        //第一天不持股，总收益为0
        dp[0][0] = 0; 
        //第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0]; 
        //遍历后续每天，状态转移
        for(int i = 1; i < n; i++){ 
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], -prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0]; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(n)，其中n为数组长度，遍历一次数组
空间复杂度：O(n)，动态规划辅助数组的空间

解法二:贪心

如果我们在某一天卖出了股票，那么要想收益最高，一定是它前面价格最低的那天买入的股票才可以。因此我们可以利用贪心思想解决，每次都将每日收入与最低价格相减维护最大值。

• 首先排除数组为空的特殊情况。
• 将第一天看成价格最低，后续遍历的时候遇到价格更低则更新价格最低。
• 每次都比较最大收益与当日价格减去价格最低的值，选取最大值作为最大收益。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //维护最大收益
        int res = 0; 
        //排除特殊情况
        if(prices.size() == 0) 
            return res;
        //维护最低股票价格
        int Min = prices[0]; 
        //遍历后续股票价格
        for(int i = 1; i < prices.size(); i++){ 
            //如果当日价格更低则更新最低价格
            Min = min(Min, prices[i]); 
            //维护最大值
            res = max(res, prices[i] - Min); 
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n)，其中n为数组长度，一次遍历数组
空间复杂度：O(1)，常数级变量，无额外辅助空间