什么是动态规划

百度百科解释如下：

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
基本思想与策略编辑:
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

一篇动态规划 博客 阐述如下：

首先是拆分问题，根据问题的可能性把问题划分成一步一步，这样就可以通过递推或者递归来实现.
关键就是这个步骤，动态规划有一类问题就是从后往前推到，有时候我们很容易知道:如果只有一种情况时，最佳的选择应该怎么做。然后根据这个最佳选择往前一步推导，得到前一步的最佳选择
然后就是定义问题状态和状态之间的关系，我的理解是前面拆分的步骤之间的关系，用一种量化的形式表现出来，类似于高中学的推导公式,因为这种式子很容易用程序写出来，也可以说对程序比较亲和(也就是最后所说的状态转移方程式)
我们再来看定义的下面的两段，我的理解是比如我们找到最优解,我们应该讲最优解保存下来，为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解，此时我们应该放弃，只保存最优解，这样我们每一次都把最优解保存了下来，大大降低了时间复杂度。

动态规划与分治法的区别在于划分的子问题是有重叠的，解过程中对于重叠的部分只要求解一次，记录下结果，减少了重复计算过程。
另外，DP在求解一个问题最优解时，不是固定的计算合并某些子问题的解，而是根据各子问题的解的情况选择其中最优的。
动态规划求解具有以下性质：
最优子结构性质：最优解包含了其子问题的最优解，不是合并所有子问题的解，而是找最优的一条解线路，选择部分子最优解来达到最终的最优解。
子问题重叠性质：先计算子问题的解，再由子问题的解去构造问题的解（由于子问题存在重叠，把子问题解记录下来为下一步使用，这样就可以从备忘录中读取）。其中备忘录先记录初始状态。

刷题记录

最长递增子序列

描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

LeetCode 链接：https://leetcode.cn/problems/longest-increasing-subsequence

思路

令状态 dp[i] 表示以 nums[i] 作为末尾的最长递增子序列的长度，考虑边界情况，dp[0] = 1，状态转移方程 dp[i] = max(dp[j]) +1，其中 0<=j<i 且 num[j]<num[i] ，考虑在 j = 0…i-1 取一个最大子序列长度时，因为要求 num[i] 结尾，序列要求递增，则必须 num[i] > num[j]。

最后，整个数组的最长上升子序列即 dp 数组的最大值。

题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        dp.push_back(1);
        int dp_max = 1;
        for(int i = 1; i < nums.size(); i++){
            int temp = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    temp = max(temp, dp[j]+1);
                }
            }
            dp.push_back(temp);
            dp_max = max(dp_max, temp);
        }
        return dp_max;
    }
};

最大连续子序列和

描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

LeetCode 链接：https://leetcode.cn/problems/maximum-subarray/

思路

令状态 dp[i] 表示以 nums[i] 作为末尾的连续序列的最大和，考虑边界情况，dp[0] = nums[0]，状态转移方程 dp[i] = max(nums[i], dp[i-1] + nums[i])，因为是以 nums[i] 结尾，max 的作用其实就是取舍上一个状态，如果上一个状态小于等于 0，dp[i] = nums[i]。

求 dp[i] 的同时可以做比较，避免二次循环。

题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp;
        dp.push_back(nums[0]);
        int dp_max = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp.push_back(max(nums[i], nums[i]+ dp[i-1]));
            if(dp_max < dp[i]){
                dp_max = dp[i];
            }
        }
        return dp_max;
    }
};

买卖股票的最佳时机

描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

LeetCode 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock

思路

如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

LeetCode-Solution 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/

题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1){
            return 0;
        }
        int min_v = prices[0], max_b = 0;
        for(int i = 1; i < prices.size(); i++){
            max_b = max(max_b, prices[i] - min_v);
            min_v = min(min_v, prices[i]);
        }
        return max_b;
    }
};

卖股票的最佳时机 II

直接参考：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

UVA 12034 Race

描述

n 匹马，共有多少种排名情况（可以并列）

UVA 链接：https://vjudge.net/problem/UVA-12034

思路

参考链接：https://blog.csdn.net/qq_39479426/article/details/81229724

dp[i][j] 表示 i 匹马占有 j 个名次的组合情况

然后考虑 i 匹马和 i-1 匹马的转移关系，多了一匹马要放在哪个位置，有下面两种情况

第 i 匹马和前 i-1 匹马中至少一匹马的成绩相同（j 个名次就有 j 种情况）
这匹马独占了一个成绩（可以放入 j 个位置，注意这里不是 j+1）
所以可以得到递推式：dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1] * 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<string.h>
using namespace std;
 
long long dp[1050][1050];   //dp[i][j]表示i只马占有j个名次(i>=j)
long long fac[1000];
void solve()
{
    fac[0] = 1; fac[1] = 1;
    # 求阶乘，i == j = A 时，组合情况就是 A！
    for (int i = 2; i <= 1000; i++)
        fac[i] = (i * fac[i - 1]) % 10056;
 
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= 1000; i++)
        dp[i][1] = 1;
 
    for (int i = 2; i <= 1000; i++)
    {
        for (int j = 2; j <= i; j++)
        {
            if (i - 1 >= j)
            //前i-1只马用完了j个名次,最后一只马有j种选择; 前面i-1只马用了j-1个名次,(j-1)最后一只马独占一个名次,同样有j种选择
                dp[i][j] = (dp[i - 1][j] * j + dp[i - 1][j - 1] * j) % 10056;
            else if (i == j)
                dp[i][j] = fac[i];
        }
    }
}
 
int main()
{
    solve();
 
    int T;
    scanf("%d", &T);
    int k = 1;
    while (T--)
    {
        int n;
        scanf("%d", &n);
        long long sum = 0L;
        for (int i = 1; i <= n; i++)
            sum = (sum + dp[n][i]) % 10056;
        printf("Case %d: %lld\n", k++, sum);
    }
 
    return 0;
}

0/1 背包问题

描述

给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

题解
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream> 
#include <algorithm>
using namespace std;
//记忆性数组动态规划解法 
int packageSolution(int n, int pc, int gvol[], int gval[]){
	//用 dp[i][j] 表示，取前 i 种物品，总体积不超过 j 的所能取得的最大价值总量 
	int dp[n+1][pc+1];
	// 初始化边界条件，也就是第一行，取前 1 种物品，总体积不超过 j 的最大价值总量 
	for(int j = 0; j <= pc; j++){
		if(gvol[1]<=j) {
			dp[1][j] = gval[1];
		}else{
			dp[1][j] = 0;
		}
	}
	for(int i = 2; i <= n; i++){
		for(int j = 0 ;j <= pc; j++){
			// dp[i-1][j] 表示不取第 i 种物品的最大价值
			// dp[i-1][j-gvol[i]] + gval[i] 表示取第 i 种物品的最大价值，认真想一下 dp[i][j] i、j 分别表示啥意思，就知道为啥需要 dp[i][j-gvol[i]] 了，体会状态转化的思想
			// 只有  (j - gvol[i])>=0 才能取第 i 种 
			if((j - gvol[i])>=0){
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-gvol[i]] + gval[i]);
			}else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	return dp[n][pc];
}

int main(){
	//物品个数，背包容量 
	int n, package_capacity;
	//输入一行，两个数字以空格间隔 
	cin>>n>>package_capacity;
	
	//物品体积数组、物品价值数组 
	int goods_volumn[n+1], goods_value[n+1];
	for(int i = 1; i <= n; i++){
		//输入 n 行，每行两个数字以空格间隔 
		cin>>goods_volumn[i]>>goods_value[i];
	}
	// 以 3 个物体，背包容量为 5 为例
	//三个物体的体积、价值依次是
	//1 3 
	//2 1
	//3 2 
	// 那么会选择第一个和第三个物品，最大价值和为 3+2=5 
	cout<<"the max total value: "<<packageSolution(n, package_capacity, goods_volumn, goods_value);
	return 0;
}

参考材料

1、北京大学郭炜 MOOC 慕课：https://www.icourse163.org/learn/PKU-1001894005