动态规划（一）

📝算法介绍

动态规划（Dynamic programming）常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

---

👉一个例题

题号：soj 1176 --Two Ends
题目：给一个长度为n的数列ai，两个人在上面做交替取数，每个人的每一轮从这个数列的两端中取出一个数（不能不操作）。先手可以自由选择策略，后手选择贪心策略。贪心策略是指，如果两端数大小不同，选择大的那个；如果相同选择左边那个。问最后先手能赢后手多少分。(1<=n<=1000且n为偶数)

我们定义一个二维数组values储存所有的解的情况，定义一维数组num储存数字序列；然后定义动态规划函数dp(int left, int right)，其中left, right分别表示左右边界的牌，玩家每一次选择都有两种情况：选择最左边的牌或最右边的牌。故每一次动态规划都有两种方案：

• 第一种，先手选择最左边的牌left，那么后手就会进行贪心算法选择剩下的左右边界中最大的那张牌，如果最左边大，则后手取走牌left+1，下一次dp序列为left+2到right；如果最右边大，则后手取走牌right，下一次dp序列为left+1到right-1；
  
• 第二种，先手选择最右边的牌right，那么后手就会进行贪心算法选择剩下的左右边界中最大的那张牌，如果最左边大，则后手取走牌left，下一次dp序列为left+1到right-1；如果最右边大，则后手取走牌right-1，下一次dp序列为left到right-2；
  

每一次dp都对上述两种方案进行比较，选择先手分值比较高的方案对values[left][right]进行赋值，最终找出最好的方案。

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1000;
int num[maxn];
int values[maxn][maxn];

int dp(int left, int right) {//参数都是index
	if (left > right)	return 0;
	if (values[left][right] != -1)	return values[left][right];
	values[left][right] = 0;

	values[left][right] = max(values[left][right], num[left+1] >= num[right] ? num[left]+dp(left+2,right) : num[left]+dp(left+1,right-1));//先手拿了左边
	values[left][right] = max(values[left][right], num[left] >= num[right-1] ? num[right]+dp(left+1,right-1) : num[right]+dp(left,right-2));//先手拿了右边
	return values[left][right];
}

int main() {
	int n;
	int count = 0;
	while (cin >> n && n) {
		count++;
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			cin >> num[i];
			sum += num[i];
			for (int j = 0; j < n; ++j) {
				values[i][j] = -1;
			}
		}
		cout << "In game " << count << ", the greedy strategy might lose by as many as " << 2*dp(0, n - 1)-sum << " points." << endl;
	}
	return 0;
}

---

👉另一个例题

题号：soj 1011 --Lenny's Lucky Lotto
题目：给定N，M，问有多少个长度为N的整数序列，满足所有数都在[1,M]内，并且后一个数都至少是前一个数的两倍。

用f[i][j]表示长度为i，最大数为j的序列的数目；用s[i][j]表示长度为i，最大数不超过j的序列的数目，那么可以推出：s[i][j]=s[i][j-1]+f[i][j]、f[i][j]=s[i-1][j/2]。

在这组递推式中我们进行了记忆存储，长度每增加1，利用已记录的原长度的相关数据简单计算得到新长度的数据并记录，自底向上递推。

long long dp(int n, int m) {
	long long s[11][2001] = {0};
	long long f[11][2001] = {0};
	for (int j = 1; j <= m; ++j) {
		f[1][j] = 1;
		s[1][j] = j;
	}
	for (int i = 2; i <= n; ++i) {
		f[i][0] = s[i][0] = 0;
		for (int j = 1; j <= m; ++j) {
			f[i][j] = s[i-1][j/2];
			s[i][j] = s[i][j-1] + f[i][j];
		}
	}
	return s[n][m];
}

❗ Sicily的题设中意于很大的数，所以写的时候注意看看需不需要把int改成long long（没错我就时常因为这个问题WA）。

---

📝小结

可见，上述例题最主要的共同点：记忆存储，即建立二维数组->代入参数->逐层递推的过程。这是动态规划问题最常见的套路之一。