发表于   |   分类于   |  

题目大意

　　http://acm.hdu.edu.cn/showproblem.php?pid=2602

　　0-1背包问题，本题的练习主要体会01背包的存储优化，由二维数组降至一维数组，因为每次dp[i][j]总是依赖于dp[i-1][x]因此不需要将所有dp[i][j]的所有值都保存下来。

代码

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 1005
int dp[MAX_SIZE];
int value[MAX_SIZE];
int volume[MAX_SIZE];
int main() {
    int T;
    scanf("%d", &T);
    for(int t = 0; t < T; t++) {
        int N, V;
        scanf("%d%d", &N, &V);
        for(int i = 1; i <= N; i++) {
            scanf("%d", &value[i]);
        }
        for(int i = 1; i <= N; i++) {
            scanf("%d", &volume[i]);
        }
        memset(dp, 0, sizeof(dp));
        //i >= 1
        for(int i = 1; i <= N; i++) {
            for(int j = V; j >= volume[i]; j--) { //注意从大到小遍历
                int a = dp[j];
                int b = dp[j - volume[i]] + value[i];
                dp[j] = a > b ? a : b;
            }
           
        }
        printf("%d\n", dp[V]);
    }
    return 0;
}

　　注意此行for(int j = V; j >= volume[i]; j--)一定要从V往小值的方向遍历，因为我们每次需要依赖上次保存的dp值，并且更新dp值，a和b的右侧dp值均是上次循环的dp值。如果for循环j从小值往大的方向遍历，那么小的dp[j]的值先会被更新，那么大的j的值对应的dp值在更新时，如果依赖于下标小的dp值时，就不是上次循环的dp值，因此要从大往小遍历。

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/house-robber-ii/

　　一个强盗可以对一条环上每户人家进行抢劫，每家可以获得不同数量的钱财，但是要求相邻的两家不能同时抢劫，问强盗最多可以抢到多少钱财

题目分析

　　这个题是house robber的变形，之前house robber的解题思路是这样的：

　　跟背包问题思路有点像，用m数组表示处理完第i家以后获得的最大价值，v代表每家的价值。当强盗走到第i家门前时，他的选择是抢或者不抢。如果抢劫的话，那么他能获得的价值是m[i - 2] + v[i]，即便第i-1家已经抢过，也可以重置一下，不抢第i-1家，抢第i家。如果不抢的话，那么就是m[i-1]，转移方程为：

m[i] = max{m[i-1],m[i-2]+v[i]}

　满足动态规划的条件：最优子结构性质，m[i]是最优方案，那么m[j] (任意 j<i) 也一定是最优方案

　　成环以后要求不变，抢劫的不能相邻，要把环的问题化成直线，把第0户人家和第n-1户人家拆开，因为最后的方案中一定是不能同时选择第0户和第n-1户，因此最后的最优方案一定在抢劫0~(n-2)户，和抢劫1~(n-1)户的最优解中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int rob(vector<int>& nums) {
        int s = nums.size();
        if(s == 0) return 0;//注意边界处理
        if(s == 1) return nums[0];//注意边界处理
        if(s == 2) return (nums[0] > nums[1]) ? nums[0] : nums[1];//注意边界处理
        int v1 = robRange(nums, 1, s - 1);
        int v2 = robRange(nums, 0, s - 2);
        return (v1 > v2) ? v1 : v2;
    }
private:
    int robRange(vector<int>& num, int l, int r) {
        int prepre = 0, pre = 0;
        for(int i = l; i <= r; i++) {
            int maxv = std::max(prepre + num[i], pre);
            prepre = pre;
            pre = maxv;
        }
        return pre;
    }
};

　　这里的解法仅仅是求出了最优值，没有对中间的具体抢劫方案进行记录，时间复杂度O(n)，额外空间复杂度是O(1)

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/house-robber/

　　一个强盗可以对一条街上每户人家进行抢劫，每家可以获得不同数量的钱财，但是要求相邻的两家不能同时抢劫，问强盗最多可以抢到多少钱财

题目分析

　　跟背包问题思路有点像，用m数组表示处理完第i家以后获得的最大价值，v代表每家的价值。当强盗走到第i家门前时，他的选择是抢或者不抢。如果抢劫的话，那么他能获得的价值是m[i - 2] + v[i]，即便第i-1家已经抢过，也可以重置一下，不抢第i-1家，抢第i家。如果不抢的话，那么就是m[i-1]，转移方程为：

　　m[i] = max{m[i-1],m[i-2]+v[i]}

　　满足动态规划的条件：最优子结构性质，m[i]是最优方案，那么m[j] (任意 j<i) 也一定是最优方案

代码

1
2
3
4
5
6
7
8
9
int robRange(vector<int>& num, int l, int r) { //抢劫范围是l~r的闭区间
    int prepre = 0, pre = 0;
    for(int i = l; i <= r; i++) {
        int maxv = std::max(prepre + num[i], pre);
        prepre = pre;
        pre = maxv;
    }
    return pre;
}

　　这里的解法仅仅是求出了最优值，没有对中间的具体抢劫方案进行记录，时间复杂度O(n)，额外空间复杂度是O(1)

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/best-time-to-buy-and-sell-stock//

　　你有n天股票的价格，现在可以选择在某天买入，某天卖出，求出能获得的最大利润

题目分析

　　数组s[i]代表可选天数是1~i天时，能获得的股票最大利润

　　s[i]=max{ max{ (v[i] - min{v[0]....v[i-1]}), 0 }, s[i-1] }

　　满足动态规划的条件

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxProfit(vector<int>& prices) {
    int s = prices.size();
    if(s < 2) return 0;
    int pre = 0;
    int minp = prices[0];
    for(int i = 1; i < s; i++) {
        int v1 = prices[i] - minp;
        if(v1 < 0) {
            v1 = 0;
        }
        int v2 = pre;
        if(prices[i] < minp) {
            minp = prices[i];
        }
        pre = (v1 > v2) ? v1 : v2;
    }
    return pre;
}

　　时间复杂度O(n)，额外空间复杂度O(1)