算法——动态规划例题代码（OJ测试通过）

很久没更新了，我不会告诉你我是因为找不到原题……

动态规划就是保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。

用强迫症的话说就是，不管中途答案是什么，直接存起来，否则漏掉一个两个搞得不顺滑了，就心里难受。而且一般是二维数组按顺序（可能是位置也可能是次序）存起来。

废话会云不云，直接上题目。

题一  计算从三角形顶到底的一条路径，使该路径走过的数字总和最大

问题描述：给定一个由n行数字组成的数字三角形，如下:

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5

试设计一个算法，计算从三角形顶到底的一条路径，使该路径走过的数字总和最大。

算法设计：对于给定n行数字组成的数字三角形，计算从三角形顶到底的经过数字和最大的路径.

输入

第一行是数字三角形的行数n，1<=n<=100。

接下来n行，是数字三角形各行中的数字，所有数字在0~99之间。

输出

计算出的最大值

样例输入

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

样例输出

30

废话不多说，代码如下：

#define _CRT_SECURE_NO_WARNINGS//VS2019需要加上
#include<stdio.h>
 
#define MAX 102
int D[MAX][MAX];
int n;
int maxSUM[MAX][MAX];
 
int max(int i, int j)//求二者之间的最大值
{
	return i > j ? i: j;
}
 
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &D[i][j]);//正三角输入
	for (int i = 1; i <= n; i++)
		maxSUM[n][i] = D[n][i];//最后一行因为没有下一行了，直接复制过来
	for (int i = n - 1; i >= 1; i--)//题目是从上往下走，但是一旦确定路线之后从上往下和从下往上路径的加和是一样的，那就从下往上算
		for (int j = 1; j <= i; j++)//对于除了最后一行之外的其他行都有下一行
			maxSUM[i][j] = max(maxSUM[i + 1][j], maxSUM[i + 1][j + 1]) + D[i][j];//下一行和本行的加和找最大值替换掉当前值
	printf("%d\n", maxSUM[1][1]);//一直反复操作到三角形左上角尖，就是所有路径的最大值
	return 0;
}

题二  长江游艇俱乐部问题

问题描述：长江游艇俱乐部在长江上设置了n个游艇出租站1，2，....，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j)，1<=i<=j<=n。试设计一个算法，计算法出游艇出租站1到游艇出租站n的最少租金。

算法设计：对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j)，1<=i<=j<=n，计算出从游艇出租站1到游艇出租站n的最少租金

输入

第一行有一个整数n(n<=200)，表示有n个游艇出租站。

接下来n-1行表示r(i,j)，1<=i<=j<=n。

输出

输出最少租金的值

样例输入

3

5 15

7

样例输出

12

#define _CRT_SECURE_NO_WARNINGS//VS2019需要加上
#include<stdio.h>
#include<stdlib.h>
#define MAX 202
int D[MAX][MAX];
 
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <=n-1; i++)
		for (int j = i+1; j <=n; j++)//倒三角形形状的输入
			scanf("%d", &D[i][j]);
	for (int i = n-1; i >=1; i--)
	{
		for (int j = i+1; j <= n; j++)//从倒三角右下角那个尖开始
		{
			for (int k = i+1; k <j; k++)//k必须在i和j之间不能超出去
			{
				if ((D[i][k] + D[k][j]) < D[i][j])//如果从中间转换一程花费更低，就从i先到k，再从k到j
				{
					D[i][j] = D[i][k] + D[k][j];//更新从i到j的路程
				}
			}
		}
	}
	printf("%d\n", D[1][n]);//最终要找到从第1站到第n站的最少租金
	return 0;
}

题三  圆形操场的四周摆放石子问题

在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

输入

第1行是正整数n,1<=n<=100，表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。

输出

第1行的数是最小得分，第2行的数是最大得分

样例输入

3

1 2 3333

样例输出

3339

6671

#define _CRT_SECURE_NO_WARNINGS//VS2019需要加上
#include<stdio.h>
#include<stdlib.h>
#define N 450
int a[N];
int sum[N];
int min[N][N], max[N][N];
int cmin(int i, int j)//找最小值
{
	return i > j ? j : i;
}
int cmax(int i, int j)//找最大值
{
	return i > j ? i : j;
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		a[i + n] = a[i];//用直线模拟圆环
	}
	for(int i=0;i<N;i++)
		for (int j = 0; j < N; j++)//给最小值数组和最大值数组赋初值
		{
			min[i][j] = 0x3f3f3f3f;
			max[i][j] = -1;
		}
	for (int i = 1; i <= 2 * n; i++)
	{
		min[i][i] = 0; max[i][i] = 0;//自己和自己不会合并
		sum[i] = sum[i - 1] + a[i];//本位置的总数等于前面所有位置的总数+本位置的数
	}
	for (int len = 2; len <= n; len++)//两堆石子合并，那么长度最小是2
	{
		for (int l = 1; l + len - 1 <= 2 * n; l++)
		{
			int r = l + len - 1;//根据最左侧的一堆石子和两堆之间的距离计算最右侧的石子是哪一堆
			for (int j = l; j < r; j++)//计算是当前已经有的合并方式更好还是以j为拆分点新的合并方式更好
			{
				min[l][r] = cmin(min[l][r], min[l][j] + min[j + 1][r] + sum[r] - sum[l - 1]);
				max[l][r] = cmax(max[l][r], max[l][j] + max[j + 1][r] + sum[r] - sum[l - 1]);
			}
		}
	}
	int minn = 0x3f3f3f3f, maxx = -1;//先初始化最大值最小值
	for (int i = 1; i <= n; i++)
	{
		minn = cmin(minn, min[i][i + n-1]);//计算当前最小值最小还是以新的起点开始合并得到的合并方式结果更小
		maxx = cmax(maxx, max[i][i + n-1]);//计算当前最大值最大还是以新的起点开始合并得到的合并方式结果更大
	}
	printf("%d\n%d\n", minn, maxx);
	return 0;
}