动态规划 | Nevermore

# 1.问题分类及求解思路

# 分类

背包问题
股票问题
子序列

# 求解

确定dp数组含义
写出递推公式
dp数组初始化
确定遍历顺序

# 2.背包问题

# 按物品可遍历次数分类

01背包：物品只能使用一次。通常先遍历物品再遍历背包，不可交换。遍历背包时倒序，不然物品回被使用多次。
完全背包：物品可以被使用无限次。背包和物品的顺序可以交换——先物品：求组合（物品有序访问，保证物品按序被访问一次）；先背包：求排列（一个背包容量可以对应多个物品的排列）。遍历背包时正序，保证物品使用多次。
多重背包：物品可以被使用有限次（>1）

# 求解的问题

一维：装满容量为i的背包最大的价值为dp[i]；二维：第i个物品装到容量为j的背包获得的最大价值为dp[i] [j]。

代码实例

一维数组

#include <iostream>
#include <vector>

int main()
{
    int time = 0;
    int goods,bagSize = 3;
    std::vector<int> cost {2, 2, 3, 1, 5, 2};
    std::vector<int> value {2, 3, 1, 5, 4, 3};
    std::vector<int> dp(bagSize + 1);
    goods = value.size();

    for (int i = 0; i < goods; i++)
    {
        for (int j = bagSize; j >= cost[i]; j--)
        {
            dp[j] = std::max(dp[j], dp[j - cost[i]] + value[i]);
        }

        if(time == 0) {
            printf("\t");
            for(int k = 0; k <= bagSize; k++) {
                printf("[%d]\t", k);
            }
            std::cout << std::endl;
        }
        time++;
        printf("(%d)\t", i);
        for(auto x : dp) {
            std::cout << x << "\t";
        }
        std::cout << std::endl;

    }
    std::cout << "背包的最大价值：" << dp[bagSize] << std::endl;
    return 0;
}

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
37

运行结果：

[z@ test]$ ./test 
	[0]	[1]	[2]	[3]	
(0)	0	0	2	2	
(1)	0	0	3	3	
(2)	0	0	3	3	
(3)	0	5	5	8	
(4)	0	5	5	8	
(5)	0	5	5	8	
背包的最大价值：8

1
2
3
4
5
6
7
8
9

背包能装的最大重量（重量=价值时）
装满容量为i的背包有dp[i]种方法：dp[j] += dp[i-value[i]] (有排列和组合数)
背包能否被装满
装满容量为j的背包，使用最小的元素个数 dp[j] = min(dp[j], dp[j-value[i]] + 1)

# 3.股票问题

股票只允许买卖一次：用二维数组表示，行表示每一天价格，列表示股票的状态（持有和不持有）。买卖一次时，计算持有的最大价值判断的是前一天持有和当天买入（-price[i]）的最大价值。
股票允许买卖多次：与买卖一次的不同点在于，当天买入的钱可以是之前买卖后的盈利，不再是0，即当天买入后的最大价值为dp[i-1] [0] - price[i]，0表示不持有（前一天不持有，当天才能买入）
至多买卖N次：数组的第二维用2N个状态表示，偶数表示买入，奇数表示卖出，0表示不操作
含有冷冻期：某一天有四个状态：当天买入（持有），当天卖出，保持前一天卖出的状态，冷冻期
有手续费

# 4.子序列

不连续递增子序列
连续递增子序列
两个数组最长重复