算法基础知识——动态规划

目录：

1. 基础知识
   1. 分治法和动态规划的区别
   2. 动态规划算法设计步骤
   3. 最优子结构性质定义
   4. 动态规划两种等价的实现方法（自顶向下带备忘、自底向上）
   5. 子问题图
2. 经典问题
   1. 钢条切割
   2. 矩阵链乘法
   3. 最大连续子序列和
   4. 最长递增子序列
   5. 最长公共子序列
   6. 0-1背包问题
   7. 完全背包问题
3. 应用实例
   1. N阶楼梯上楼问题【华中科技大学】
   2. 吃糖果【北京大学】
   3. 最大序列和【清华大学】
   4. 最大子矩阵【北京大学】
   5. 最大连续子序列【浙江大学】
   6. 拦截导弹【北京大学】
   7. 最大上升子序列和【北京大学】
   8. 方块涂色【暨南大学】
   9. 合唱队形【北京大学】
   10. Common Subsequence【Southeastern Europe 2003】
   11. Coincidence【上海交通大学】
   12. 点菜问题【北京大学】
   13. 采药【北京大学】
   14. 最小邮票数【清华大学】
   15. Piggy-Bank【Central Europe 1999】
   16. 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活【2008-06-18《 ACM程序设计》期末考试——四川加油！中国加油！】
   17. The Triangle【POJ 1163】
   18. 放苹果【北京大学】
   19. 整数拆分【清华大学】
   20. Monkey Banana Problem【light oj 1004】

一、基础知识

1、分治法和动态规划的区别：

• 分治法（Divide and Conquer）：
  • 将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。
  • 反复求解公共子子问题。
• 动态规划（Dynamic programming）：
  • 应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。
  • 对每个子子问题只求解一次，将其保存在一个表格中，从而无需每次求解一个子子问题时都重新计算。
  • 通常用于求解最优化问题（Optimization problem），找到具有最优值的解，即找到问题的一个最优解（an optimal solution），而不是最优解（the optimal solution），因为可能有多个解都达到最优值。

2、动态规划算法设计步骤：

• 刻画一个最优解的结构特征；
• 递归地定义最优解的值；
• 计算最优解的值，通常采用自底向上的办法；
• 利用计算出的信息构造一个最优解。

3、最优子结构性质（optimal substructure）：

• 问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

4、动态规划方法是付出额外的内存空间来节省计算时间，是时空权衡（time-memory trade-off）的例子，可以将一个指数时间的解转化为一个多项式时间的解。

5、动态规划两种等价的实现方法：

• 带备忘机制的自顶向下法（top-down with memoization）：
  • 按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。
  • 当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值；否则，按通常方式计算这个子问题。
• 自底向上法（bottom-up method）：
  • 需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而可以将子问题按规模排序，按由小到大的顺序进行求解。
  • 当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。
• 区别：两种方法具有相同的渐近运行时间。在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。

6、子问题图：

• 定义：一个有向图，每个顶点唯一地对应一个子问题，若求解子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。
• 特点：
  • 自底向上动态规划算法是按逆拓扑序（reverse topological sort）来处理子问题图中的顶点。
  • 带备忘机制的自顶向下动态规划算法是按照深度优先搜索（depth-first search）来处理子问题图中的顶点。
• 关系：
  • 子问题图G = (V, E)，因为每个子问题只求解一次，所以动态规划算法运行时间等于每个子问题求解时间之和。
  • 通常，一个子问题的求解时间与子问题图中对应顶点的出度成正比。
  • 动态规划算法的运行时间与顶点和边的数量呈线性关系。

二、经典问题

1、钢条切割（将长钢条切割成短钢条，使得总价值最高）

（1）思路：

• 当完成初次切割后，将两段钢条看成两个独立的钢条切割问题实例。
• 通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。

2、矩阵链乘法（用最少的标量乘法操作完成一个矩阵链相乘的运算）

（1）完全括号化：一个单一矩阵，或者是两个完全括号化的矩阵乘积链的积，且已外加括号。

• 如矩阵链为（A1，A2，A3，A4），则有五种完全括号化的矩阵乘积链：
  • （A1（A2（A3A4）））
  • （（A1（A2A3））A4）
  • （A1（（A2A3）A4））
  • （（A1A2）（A3A4））
  • （（（A1A2）A3）A4）
• 若AB = C中，A为p * q的矩阵，B为q * r的矩阵，则C为p * r的矩阵，计算C的时间为pqr。因此不同的加括号方式可能会导致不同的计算代价。

（2）思路：

• 最优化括号方案的结构特征：
  • 一个非平凡的矩阵链乘法问题实例的任何解都需要划分链，而任何最优解都是由子问题实例的最优解构成的。
  • 因此为了构造一个矩阵链乘法问题实例的最优解，我们可以将问题划分为两个子问题（AiAi+1…Ak和Ak+1Ak+2…Aj的最优括号问题），求出子问题实例的最优解，然后将子问题的最优解组合起来。
• 一个递归求子问题最优解的方案：
  • 找到最优分割点k：对于AiAi+1…Aj的最优括号化方案，k有j - i种可能取值，k = i，i + 1，…，j - 1。因此检查所有可能的情况，找到最优者。
  • m[i, j] = min{m[i, k] + m[k + 1, j] + pi-1*pk*pj}，其中i ≤ k ＜ j，若i < j；m[i, j] = 0，若i = j。
  • 用s[i, j]保存AiAi+1…Aj最优括号化方案的分割点位置k，即使得m[i, j]  = m[i, k] + m[k + 1, j] + pi-1*pk*pj成立的k值。
• 计算最优代价：
  • 过程用一个辅助表m[ 1…n, 1…n ]来保存代价m[ i, j]，辅助表s[1..n-1, 2..n]记录最优值m[i, j]对应的分割点k。

（3）递归公式：

• P(n) = 1, n = 1；P(n) = ∑(从k = 1到k = n - 1)P(k)P(n - k),n ≥ 2。

3、最大连续子序列和

• 定义：在一个给定的序列{A1, A2, ..., An}中，找出一个连续的子序列{Ai,...,Aj}，使得这个连续的子序列的和最大，输出这个最大的子序列和。
• 令dp[i]为以A[i]作为末尾的连续序列的最大和。
  • dp[i] = max{A[i], dp[i - 1] + A[i]}
• 最终最大连续子序列和为数组dp中的最大值。
• 时间复杂度：O(n)

4、最长递增子序列（Longest Increasing Subsequence，LIS）

• 定义：在一个已知序列{A1,A2,...,An}中，取出若干元素（不必连续）组成一个新的序列{Ax,...,Ay}，新序列的各个数之间依旧保持原序列中的先后顺序，此时称新序列{Ax,...,Ay}为原序列的一个子序列。若对子序列中的任意下标x < y有Ax < Ay，则称该子序列为原序列的一个递增子序列。最长递增子序列问题就是求给定序列的所有递增子序列中最长的那个子序列长度。
• 令dp[i]为以A[i]为末尾的最长递增子序列的长度。
  • dp[i] = max{1, dp[j] + 1 | j < i && Aj < Ai}
• 最终最长递增子序列的长度即为数组dp中的最大值。
• 时间复杂度：O(n²)

5、最长公共子序列（Longest Common Subsequence，LCS）

• 定义：给定两个字符串S1和S2，求一个最长公共子串，即求字符串S3，它同时为S1和S2的子串，且要求它的长度最长，并确定这个长度。
• 对于长度为n的字符串S1和长度为m的字符串S2，令dp[i][j]表示以S1[i]作为末尾和以S2[j]作为末尾的最长公共子序列的长度，则dp[n][m]的值即为最长公共子序列的长度。
  • dp[i][j] = dp[i - 1][j - 1] + 1，S1[i] = S2[j]
  • dp[i][j] = max{ dp[i - 1][j], dp[i][j - 1] }，S1[i] != S2[j]
  • 对于边界，若两个字符串中的一个为空串，则：
    • dp[i][0] = 0(0 ≤ i ≤ n)
    • dp[0][j] = 0(0 ≤ j ≤ m)
• 最终dp[n][m]中保存的值即为两个原始字符串的最长公共子序列长度。
• 时间复杂度：O(nm)

6、0-1背包问题

• 定义：有n件物品，每件物品的重量为w[i]，其价值为v[i]，现在有个容量为m的背包，如何选择物品使得装入背包物品的价值最大。
• 令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值。则dp[n][m]就是0-1背包问题的解。
  • dp[i][j] = max{ dp[i - 1][j], dp[i - 1][ j - w[i] ] + v[i] }
    • dp[i][j] = dp[i - 1][j]，第i件物品不放入
    • dp[i][j] = dp[i - 1][ j - w[i] ] + v[i]，第i件物品放入，其中j - w[i] ≥ 0，表示背包的容量可以放入第i件物品
  • 边界情况：
    • dp[i][0] = 0，0 ≤ i ≤ n
    • dp[0][j] = 0，0 ≤ j ≤ m
• 一维数组的形式：dp[j] = max{ dp[j], dp[ j - w[i] ]  + v[i] }，同时保证再每次更新中确定状态dp[j]时，dp[ j - w[i] ]未被修改，从而完成正确的状态转移。因此需要在每次更新中，倒序地遍历所有j的值。
• 最终dp[n][m]中保存的值即为0-1背包问题的解。
• 时间复杂度：O(nm)

7、完全背包问题

• 定义：有n种物品，每种物品的重量为w[i]，其价值为v[i]，每种物品的数量均为无限个，现在有容量为m的背包，如何选择物品使得装入背包的价值最大？
• 令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值。则dp[n][m]就是完全背包问题的解。
• dp[i][j] = max{ dp[i - 1][j], dp[i][ j - w[i] ] + v[i] }
  • dp[i][j] = dp[i - 1][j]，第i件物品不放入
  • dp[i][j] = dp[i][ j - w[i] ] + v[i]，第i件物品放入，其中j - w[i] ≥ 0，表示背包的容量可以放入第i件物品
• 边界情况：
  • dp[i][0] = 0，0 ≤ i ≤ n
  • dp[0][j] = 0，0 ≤ j ≤ m
• 一维数组的形式：dp[j] = max{ dp[j], dp[ j - w[i] ]  + v[i] }，同时保证再每次更新中确定状态dp[j]时，dp[ j - w[i] ]已经被修改，从而完成正确的状态转移。因此需要在每次更新中，正序地遍历所有j的值。
• 最终dp[n][m]中保存的值即为完全背包问题的解。
• 时间复杂度：O(nm)

8、多重背包问题

• 定义：有n种物品，每种物品的重量为w[i]，其价值为v[i]，每种物品的数量均为k[i]，现在有容量为m的背包，如何选择物品使得装入背包的价值最大？
• 将数量为k的物品拆分为若干组，将每组物品视为一件物品，其价值和重量为该组中所有物品的价值重量综总和。每组物品包含的原物品个数分别为2^0,2^1,2^2,...2^c-1,k-2^c+1，其中c是使得k - 2^c + 1 ≥ 0的最大整数。
  • 如k = 14，则2^0,2^1,2^2,14-2^3+1=7，所以为1,2,4,7可以表示1-14之间的任意数
  • 如k = 15，则2^0,2^1,2^2,2^3,15-2^4+1=0，所以为1,2,4,8可以表示1-15之间的任意数
  • 如k = 16，则2^0,2^1,2^2,2^3,16-2^4+1=1，所以为1,2,4,8,1可以表示1-16之间的任意数
• 时间复杂度为O(m∑log2(ki))，其中求和从i = 0到i = n。

三、应用实例

1、题目描述： N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）【华中科技大学】

• 输入格式：输入包括一个整数N(1<=N<90)。
• 输出格式：可能有多组测试数据，对于每组数据，输出当楼梯阶数是N时的上楼方式个数。
• 样例输入：
  • 4
• 样例输出：
  • 5

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 91;

long long dp[MAX_N];

int main(){
	int n;
	dp[1] = 1;
	dp[2] = 2;
	for(int i = 3; i <= MAX_N; i++){
		dp[i] = dp[i - 2] + dp[i - 1];
	}
	while(cin >> n){
		cout << dp[n] << endl;
	}
	return 0;
}

2、题目描述：名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。 妈妈告诉名名每天可以吃一块或者两块巧克力。 假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。 例如： 如果N=1，则名名第1天就吃掉它，共有1种方案； 如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案； 如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案； 如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。 现在给定N，请你写程序求出名名吃巧克力的方案数目。【北京大学】

• 输入格式：输入只有1行，即整数N。
• 输出格式：可能有多组测试数据，对于每组数据，输出只有1行，即名名吃巧克力的方案数。
• 样例输入：
  • 4
• 样例输出：
  • 5

示例代码1：

#include <iostream>

using namespace std;

const int MAX_N = 21;
long long dp[MAX_N];

int main(){
	dp[1] = 1;
	dp[2] = 2;
	for(int i = 3; i < MAX_N; i++){
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	int n;
	while(cin >> n){
		cout << dp[n] << endl;
	}
	return 0;
}

示例代码2：

#include <iostream>

using namespace std;

int result;

void DFS(int sum, int eat){
	if(sum < eat){
		return;
	}
	if(sum == eat){
		result++;
		return;
	}
	DFS(sum - eat, 1);
	DFS(sum - eat, 2);
	return;
}

int main(){
	int n;
	while(cin >> n){
		result = 0;
		DFS(n, 0);
		cout << result << endl;
	}
	return 0;
}

3、题目描述：给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。【清华大学】

• 输入格式：第一行为一个正整数N，第二行为N个整数，表示序列中的数。
• 输出格式：输入可能包括多组数据，对于每一组输入数据，仅输出一个数，表示最大序列和。
• 样例输入：
  • 5
  • 1 5 -3 2 4
  • 6
  • 1 -2 3 4 -10 6
  • 4
  • -3 -1 -2 -5
• 样例输出：
  • 9
  • 7
  • -1

示例代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> myVector;
vector<long long> dpArray;

void dp(int n){
	dpArray[0] = myVector[0];
	for(int i = 0; i < n - 1; i++){
		if(dpArray[i] + myVector[i + 1] > myVector[i + 1]){
			dpArray[i + 1] = dpArray[i] + myVector[i + 1] ;
		}else{
			dpArray[i + 1] = myVector[i + 1];
		}
	}
}


int main(){
	int n;
	while(cin >> n){
		int inputNumber;
		for(int i = 0; i < n; i++){
			cin >> inputNumber;
			myVector.push_back(inputNumber);
			dpArray.push_back(0);
		}
		dp(n);
		long long max = dpArray[0];
		for(int i = 0; i < n; i++){
			if(dpArray[i] > max){
				max = dpArray[i];
			}
		}
		cout << max << endl;
		myVector.clear();
		dpArray.clear();
	}
	return 0;
}

4、题目描述：已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。【北京大学】

• 输入格式：输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。
• 输出格式：测试数据可能有多组，对于每组测试数据，输出最大子矩阵的大小。
• 样例输入：
  • 4
  • 0 -2 -7 0
  • 9 2 -6 2
  • -4 1 -4  1
  • -1 8  0 -2
• 样例输出：
  • 15

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 101;
int a[MAX_N][MAX_N];
int aAddColumn[MAX_N];
int dp[MAX_N];
int maxValue;
int N;

void GetMAXMatrix(int col[]){
	dp[0] = col[0];
	for(int i = 1; i < N; i++){
		dp[i] = max(dp[i - 1] + col[i], col[i]);
		maxValue = max(dp[i], maxValue);
	}
}

int main(){
	while(cin >> N){
		maxValue = -127;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				cin >> a[i][j];
			}
		}
		for(int row = 0; row < N; row++){ //从第row行开始取
			for(int i = 1; i + row <= N; i++){ //每次取1行到N - row行
				memset(aAddColumn, 0, sizeof(aAddColumn));
				for(int j = 0; j < N; j++){ //每行有N列
					for(int k = 0; k < i; k++){ //把某列的行加起来
						aAddColumn[j] += a[row + k][j]; 
					}
				}
				memset(dp, 0, sizeof(dp));
				GetMAXMatrix(aAddColumn);
			}
		}
		cout << maxValue << endl;
	}
	return 0;
}

5、题目描述：给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。【浙江大学】

• 输入格式：测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K< 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。
• 输出格式：对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。
• 样例输入：
  • 6
  • -2 11 -4 13 -5 -2
  • 10
  • -10 1 2 3 4 -5 -23 3 7 -21
  • 6
  • 5 -8 3 2 5 0
  • 1
  • 10
  • 3
  • -1 -5 -2
  • 3
  • -1 0 -2
  • 0
• 样例输出：
  • 20 11 13
  • 10 1 4
  • 10 3 5
  • 10 10 10
  • 0 -1 -2
  • 0 0 0

示例代码：

#include <iostream>

using namespace std;

const int MAX_N = 10001;

struct Node{
	int dp;
	int begin;
	int end;
	Node(){};
	Node(int d, int b = 0, int e = 0):dp(d), begin(b), end(e){};
};

int input[MAX_N];
Node nodeList[MAX_N];

void MaxSequence(int n){
	nodeList[0] = Node(input[0], input[0], input[0]);
	for(int i = 1; i < n; i++){
		if(nodeList[i - 1].dp + input[i] > input[i]){
			nodeList[i] = Node(nodeList[i - 1].dp + input[i], nodeList[i - 1].begin, input[i]);
		}else{
			nodeList[i] = Node(input[i], input[i], input[i]);
		}
	}
}

int main(){
	int n;
	while(cin >> n && n != 0){
		bool flag = true;
		for(int i = 0; i < n; i++){
			cin >> input[i];
			if(input[i] > 0){
				flag = false;
			}
		}
		if(flag){
			cout << 0 << " " << input[0] << " " << input[n - 1] << endl;
		}else{
			MaxSequence(n);
			int max = -1, index = 0;
			for(int i = 0; i < n; i++){
				if(nodeList[i].dp > max){
					max = nodeList[i].dp;
					index = i;
				}
			}
			cout << max << " " << nodeList[index].begin << " " << nodeList[index].end << endl;
		}
	}
	return 0;
}

6、题目描述：某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。 【北京大学】

• 输入格式：每组输入有两行，第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
• 输出格式：每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
• 样例输入：
  • 8
  • 300 207 155 300 299 170 158 65
• 样例输出：
  • 6

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 25;

int a[MAX_N];
int dp[MAX_N];

void GetMaxSequencr(int n){
	dp[0] = 1;
	for(int i = 1; i < n; i++){
		int max = 0;
		bool flag = false;
		for(int j = 0; j < i; j++){
			if(dp[j] > max && a[j] >= a[i]){
				max = dp[j];
				flag = true;
			}
		}
		if(flag){
			dp[i] = max + 1;
		}else{
			dp[i] = 1;
		}
	}
}

int main(){
	int n;
	while(cin >> n){
		if(n == 0){
			continue;
		}
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		GetMaxSequencr(n);
		int max = dp[0];
		for(int i = 0; i < n; i++){
			if(dp[i] > max){
				max = dp[i];
			}
		}
		cout << max << endl;
	}
	return 0;
}

7、题目描述：一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。【北京大学】

• 输入格式：输入包含多组测试数据。每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。
• 输出格式：对于每组测试数据，输出其最大上升子序列和。
• 样例输入：
  • 7
  • 1 7 3 5 9 4 8
• 样例输出：
  • 18

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 1000;
int a[MAX_N];
int dp[MAX_N];

void MaxAscSequence(int n){
	for(int i = 0; i < n; i++){
		dp[i] = a[i];
		for(int j = 0; j < i; j++){
			if(a[j] < a[i]){
				dp[i] = max(dp[j] + a[i], dp[i]);
			}
		}
	}
}

int main(){
	int n;
	while(cin >> n){
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		MaxAscSequence(n);
		int max = 0;
		for(int i = 0; i < n; i++){
			if(dp[i] > max){
				max = dp[i];
			}
		}
		cout << max << endl;
	}
	return 0;
}

8、题目描述：输入格子的个数为n，刷3种颜色的颜料，相邻的格子颜料颜色不能相同，且首尾方格颜色不能相同。每个格子必须涂色。计算一共有多少种涂色方式。【暨南大学】

• 输入格式：每组测试数据占1行，包括一个正整数b(1 <= b <= 50)
• 输出格式：输出涂色方式数目
• 样例输入：
  • 1
  • 2
• 样例输出：
  • 3
  • 6

示例代码：

#include <iostream>

using namespace std;

const int MAX_N = 51;
long long dp[MAX_N];

void GetMaxPaintMethod(int n){
	dp[0] = 3;
	dp[1] = 6;
	dp[2] = 6;
	for(int i = 3; i < n; i++){
		dp[i] = dp[i - 1] + 2 * dp[i - 2];
	}
}

int main(){
	GetMaxPaintMethod(MAX_N);
	int n;
	while(cin >> n){
		cout << dp[n - 1] << endl;
	}
	return 0;
}

9、题目描述：N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK， 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【北京大学】

• 输入格式：输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
• 输出格式：可能包括多组测试数据，对于每组数据，输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
• 样例输入：
  • 8
  • 186 186 150 200 160 130 197 220
• 样例输出：
  • 4

示例代码：

#include <iostream>

using namespace std;

const int MAX_N = 101;

int dpDesc[MAX_N];
int dpAsc[MAX_N];
int stu[MAX_N];
int descAnswer;
int ascAnswer;

int GetMaxAscSequence(int n){
	if(n > 2){
		for(int i = 0; i < n; i++){
			dpAsc[i] = 1;
			for(int j = 0; j < i; j++){
				if(stu[i] > stu[j]){
					dpAsc[i] = max(dpAsc[i], dpAsc[j] + 1);
				}
			}
		}
		for(int i = n - 1; i >= 0; i--){
			dpDesc[i] = 1;
			for(int j = n - 1; j > i; j--){
				if(stu[i] > stu[j]){
					dpDesc[i] = max(dpDesc[i], dpDesc[j] + 1);
				}
			}
		}
	}
	int max = 0;
	for(int i = 0; i < n; i++){
		if(dpDesc[i] + dpAsc[i] - 1 > max){
			max = dpDesc[i] + dpAsc[i] - 1;
		}
	}
	return max;
}

int main(){
	int n;
	while(cin >> n){
		for(int i = 0; i < n; i++){
			cin >> stu[i];
		}
		int answer = n - GetMaxAscSequence(n);
		cout << answer << endl;
	}
	return 0;
}

10、题目描述：A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.【Southeastern Europe 2003】

• 输入格式：The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces.The input data are correct.
• 输出格式：For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. 
• 样例输入：
  • abcfbc abfcab
  • programming contest 
  • abcd mnp
• 样例输出：
  • 4
  • 2
  • 0

示例代码：

#include <iostream>
#include <string>

using namespace std;

const int MAXN = 500;

int dp[MAXN][MAXN];

int main(){
	string s1, s2;
	while(cin >> s1 >> s2){
		s1 = " " + s1;
		s2 = " " + s2;
		for(int i = 0; i < s1.size(); i++){
			for(int j = 0; j < s2.size(); j++){
				if(i == 0 || j == 0){
					dp[i][j] = 0;
				}else if(s1[i] != s2[j]){
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}else{
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
			}
		}
		cout << dp[s1.size() - 1][s2.size() - 1] << endl;
	}
	return 0;
}

11、Find a longest common subsequence of two strings.【上海交通大学】

• 输入格式：First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
• 输出格式：For each case, output k – the length of a longest common subsequence in one line.
• 样例输入：
  • abcd
  • cxbydz
• 样例输出：
  • 2

示例代码：

#include <iostream>
#include <string>

using namespace std;

const int MAX_N = 101;
int dp[MAX_N][MAX_N];

int main(){
	string s1, s2;
	while(cin >> s1 >> s2){
		s1 = " " + s1;
		s2 = " " + s2;
		for(int i = 0; i < s1.size(); i++){
			for(int j = 0; j < s2.size(); j++){
				if(i == 0 || j == 0){
					dp[i][j] = 0;
				}else if(s1[i] == s2[j]){
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}else{
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		cout << dp[s1.size() - 1][s2.size() - 1] << endl;
	}
	return 0;
}

12、北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。注意：由于需要营养多样化，每种菜只能点一次。【北京大学】

• 输入格式：输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。
• 输出格式：输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。
• 样例输入：
  • 90 4
  • 20 25
  • 30 20
  • 40 50
  • 10 18
  • 40 2
  • 25 30
  • 10 8
• 样例输出：
  • 95
  • 38

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_VALUE = 1001;
const int MAX_DISH = 101;

int dish[MAX_DISH][2];
int dp[MAX_VALUE];

int main(){
	int v, d;
	while(cin >> v >> d){
		for(int i = 0; i < d; i++){
			cin >> dish[i][0] >> dish[i][1];//价格 评分
		}
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < d; i++){
			for(int j = v; j >= dish[i][0]; j--){
				dp[j] = max(dp[j], dp[j - dish[i][0]] + dish[i][1]);
			}
		}
		cout << dp[v] << endl;
	}
}

13、题目描述：辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。 为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。 医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。 我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？【北京大学】

• 输入格式：输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
• 输出格式：可能有多组测试数据，对于每组数据，输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
• 样例输入：
  • 70 3
  • 71 100
  • 69 1
  • 1 2
• 样例输出：
  • 3

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_TIME = 1001;
const int DRUG_NUMBER = 101;

int dp[MAX_TIME];
int times[DRUG_NUMBER];
int values[DRUG_NUMBER];

int main(){
	int T, M;//采药的时间和草药的数目
	while(cin >> T >> M){
		for(int i = 0; i < M; i++){
			cin >> times[i] >> values[i];
		}
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < M; i++){
			for(int j = T; j >= times[i]; j--){
				dp[j] = max(dp[j], dp[j - times[i]] + values[i]);
			}
		}
		cout << dp[T] << endl;
	}
	return 0;
}

14、题目描述：有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。     如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。【清华大学】

• 输入格式：有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
• 输出格式：对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
• 样例输入：
  • 10
  • 5
  • 1 3 3 3 4
• 样例输出：
  • 3

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_STAMP = 21;
const int MAX_VALUE = 101;

int dp[MAX_VALUE];
int stamp[MAX_STAMP];

int main(){
	int totalValue, stampNumber;
	while(cin >> totalValue >> stampNumber){
		for(int i = 0; i < stampNumber; i++){
			cin >> stamp[i];
		}
		for(int i = 0; i <= totalValue; i++){
			dp[i] = MAX_VALUE;
		}
		dp[0] = 0;
		for(int i = 0; i < stampNumber; i++){
			//能够凑成，且数量变少就取代
			for(int j = totalValue; j >= stamp[i]; j--){
				if(dp[j - stamp[i]] == MAX_VALUE){
					continue;
				}
				if(dp[j - stamp[i]] + 1 < dp[j]){
					dp[j] = dp[j - stamp[i]] + 1;
				}
			}
		}
		if(dp[totalValue] == MAX_VALUE){
			cout << 0 << endl;
		}else{
			cout << dp[totalValue] << endl;
		}
	}
	return 0;
}

15、题目描述：Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank（储钱罐）. You know that this process is irreversible（不可逆的）, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely（过早地） broken pigs!【Central Europe 1999】

• 输入格式：The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, P and W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units（货币单位）, W is it's weight in grams.
• 输出格式：Print exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.".
• 样例输入：
  • 3
  • 10 110
  • 2
  • 1 1
  • 30 50
  • 10 110
  • 2
  • 1 1
  • 50 30
  • 1 6
  • 2
  • 10 3
  • 20 4
• 样例输出：
  • The minimum amount of money in the piggy-bank is 60.【2个价值为30，重为50的硬币】
  • The minimum amount of money in the piggy-bank is 100.【100个价值为1元，重为1g的硬币】
  • This is impossible.

示例代码：

#include <iostream>

using namespace std;

const int MAX_WEIGHT = 100001;
const int COIN_TYPE = 501;
const int INF = 0x1fffffff;

int pValue[COIN_TYPE];
int weight[COIN_TYPE];

int dp[MAX_WEIGHT];

int main(){
	int emptyPot, fullPot, coinType;
	int caseNumber;
	while(cin >> caseNumber){
		for(int currCase = 0; currCase < caseNumber; currCase++){
			cin >> emptyPot >> fullPot >> coinType;
			for(int i = 0; i < coinType; i++){
				cin >> pValue[i] >> weight[i];
			}
			int potVolume = fullPot - emptyPot;
			for(int i = 0; i <= potVolume; i++){
				dp[i] = INF;
			}
			dp[0] = 0;
			for(int i = 0; i < coinType; i++){
				for(int j = weight[i]; j <= potVolume; j++){
					dp[j] = min(dp[j], dp[j - weight[i]] + pValue[i]);
				}
			}
			if(dp[potVolume] == INF){
				cout << "This is impossible." << endl;
			}else{
				cout << "The minimum amount of money in the piggy-bank is " << dp[potVolume] << "." << endl;
			}
		}
	}
	return 0;
}

16、题目描述：急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？
后记：
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活——
感谢父母，他们给予我们生命，抚养我们成人；
感谢老师，他们授给我们知识，教我们做人
感谢朋友，他们让我们感受到世界的温暖；
感谢对手，他们令我们不断进取、努力。
同样，我们也要感谢痛苦与艰辛带给我们的财富～【2008-06-18《 ACM程序设计》期末考试——四川加油！中国加油！】

• 输入格式：输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
• 输出格式：对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
• 样例输入：
  • 1
  • 8 2
  • 2 100 4
  • 4 100 2
• 样例输出：
  • 400

示例代码：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_N = 101 * 20;
int dp[MAX_N];
int w[MAX_N];
int v[MAX_N];
vector<int> tmpList;

vector<int> getList(int n){
	tmpList.clear();
	if(n == 1){
		tmpList.push_back(1);
	}else{
		int tmp = 1, count = n;
		while(tmp <= count){
			tmpList.push_back(tmp);
			count -= tmp;
			tmp *= 2;
		}
		if(count != 0){
			tmpList.push_back(count);
		}
	}
	return tmpList;
}

int main(){
	int caseNumber, money, category, weight, value, bagNumber;
	while(cin >> caseNumber){
		for(int m = 0; m < caseNumber; m++){
			cin >> money >> category;
			int index = 0;
			for(int i = 0; i < category; i++){
				cin >> value >> weight >> bagNumber;
				vector<int> list = getList(bagNumber);
				for(int j = 0; j < list.size(); j++){
					v[index] = list[j] * value;
					w[index] = list[j] * weight;
					index++;
				}
			}
			memset(dp, 0, sizeof(dp));
			for(int i = 0; i < index; i++){
				for(int j = money; j >= v[i]; j--){
					dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
				}
			}
			cout << dp[money] << endl;
		}
	}
	return 0;
}

17、题目描述：Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally（对角线） down to the left or diagonally down to the right.【POJ 1163】

• 输入格式：Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
• 输出格式：Your program is to write to standard output. The highest sum is written as an integer.
• 样例输入：
  • 5
  • 7
  • 3 8
  • 8 1 0 
  • 2 7 4 4
  • 4 5 2 6 5
• 样例输出：
  • 30

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 101;
int a[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

int main(){
	int number;
	while(cin >> number){
		memset(a, 0, sizeof(a));
		int row = 1;
		while(row <= number){
			for(int j = 1; j <= row; j++){
				cin >> a[row][j];
			}
			row++;
		}
		for(int i = 1; i <= number; i++){
			for(int j = 1; j <= number; j++){
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
			}
		}
		int max = 0;
		for(int j = 1; j <= number; j++){
			if(dp[number][j] > max){
				max = dp[number][j];
			}
		}
		cout << max << endl;
	}
	return 0;
}

18、把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。【北京大学】

• 输入格式：每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
• 输出格式：对输入的每组数据M和N，用一行输出相应的K。
• 样例输入：
  • 7 3
• 样例输出：
  • 8

示例代码：

#include <iostream>

using namespace std;

const int MAX_N = 11;

int main(){
	int M, N;//M个苹果，N个盘子
	int dp[MAX_N][MAX_N];
	while(cin >> M >> N){
		for(int i = 0; i <= M; i++){
			for(int j = 0; j <= N; j++){
				if(i == 0 || j == 0 || i == 1 || j == 1){
					dp[i][j] = 1;
					continue;
				}
				if(i < j){
					dp[i][j] = dp[i][i];
				}else{
					dp[i][j] = dp[i - j][j] + dp[i][j - 1];
				}
			}
		}
		cout << dp[M][N] << endl;
	}
	return 0;
}

19、一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。 用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。【清华大学】

• 输入格式：每组输入包括一个整数：N(1<=N<=1000000)。
• 输出格式：对于每组数据，输出f(n)%1000000000。
• 样例输入：
  • 7
• 样例输出：
  • 6

示例代码：

#include <iostream>

using namespace std;

const int MAX_N = 1000001;
const int MOD = 1000000000;

int weight[25];
int dp[MAX_N];

int main(){
	int n;
	int index = 0;
	for(int i = 1; i < MAX_N; i *= 2){
		weight[index++] = i;
	}
	dp[0] = 1;
	for(int i = 0; i < index; i++){
		for(int j = weight[i]; j <= MAX_N; j++){
			dp[j] = (dp[j - weight[i]] % MOD + dp[j] % MOD) % MOD;
		}
	}
	while(cin >> n){
		cout << dp[n] << endl;
	}
	return 0;
}

20、题目描述：You are in the world of mathematics to solve the great "Monkey Banana Problem". It states that, a monkey enters into a diamond shaped two dimensional array and can jump in any of the adjacent cells down from its current position (see figure). While moving from one cell to another, the monkey eats all the bananas kept in that cell. The monkey enters into the array from the upper part and goes out through the lower part. Find the maximum number of bananas the monkey can eat.【light oj 1004】

• 输入格式：Input starts with an integer T (≤ 50), denoting the number of test cases.Every case starts with an integer N (1 ≤ N ≤ 100). It denotes that, there will be 2*N - 1 rows. The i^th(1 ≤ i ≤ N) line of next N lines contains exactly i numbers. Then there will be N - 1 lines. The j^th(1 ≤ j < N) line contains N - j integers. Each number is greater than zero and less than 2^15.
• 输出格式：For each case, print the case number and maximum number of bananas eaten by the monkey.
• 样例输入：
  • 2
  • 4
  • 7
  • 6 4
  • 2 5 10
  • 9 8 12 2
  • 2 12 7
  • 8 2
  • 10
  • 2
  • 1
  • 2 3
  • 1
• 样例输出：
  • Case 1: 63
  • Case 2: 5

示例代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 101;

int main(){
	int caseNumber, row;
	cin >> caseNumber;
	int dp[MAX_N][MAX_N];
	int banana[MAX_N][MAX_N];
	for(int c = 1; c <= caseNumber; c++){
		memset(banana, 0, sizeof(banana));
		memset(dp, 0, sizeof(dp));
		cin >> row;
		for(int i = 1; i <= row; i++){
			for(int j = 1; j <= i; j++){
				cin >> banana[i][j];
			}
		}
		for(int i = row + 1; i <= 2 * row - 1; i++){
			for(int j = 1; j <= 2 * row - i; j++){
				cin >> banana[i][j];
			}
		}
		for(int i = 1; i <= row; i++){
			for(int j = 1; j <= row; j++){
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + banana[i][j];
			}
		}
		for(int i = row + 1; i <= 2 * row - 1; i++){
			for(int j = 1; j <= row; j++){
				dp[i][j] = max(dp[i - 1][j + 1], dp[i - 1][j]) + banana[i][j];
			}
		}
		cout << "Case " << c << ": " << dp[2 * row - 1][1] << endl;
	}
	return 0;
}

参考文献：

[1]Thomas.H.Cormen Charles E. Leiseron、Ronald L. Rivest Clifford Srein. 算法导论（第3版）. [M]北京：机械工业出版社，2013.01；
[2]杨泽邦、赵霖. 计算机考研——机试指南（第2版）. [M]北京：电子工业出版社，2019.11；