实验名称： 动态规划
一、实验预习
1、实验目的
1. 理解并掌握动态规划方法的设计思想；
2. 提高应用动态规划方法解决问题和设计算法的能力；
3. 通过编程实现租用游艇问题和石子合并问题，进一步理解动态规划方法解题的四个基本步骤。
2、实验内容
1. 租用游艇问题：长江游艇俱乐部在长江上设置了 n 个游艇出租站 1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i, j), 1≤i<j≤n。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。
两个测试用例：输入数据分别由文件名为 input 1.txt和input 2.txt的文本文件提供，文件的第一行中有 1 个正整数 n（n<=200），表示有 n个游艇出租站。接下来的 n-1 行是 r(i, j), 1≤i<j≤n。请分别计算并给出结果。
2. 石子合并问题：在一个操场上一排地摆放着 n 堆石子。要求将这些石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将 n 堆石子合并成一堆的最小得分。
两个测试用例：输入数据分别由文件名为 input 1.txt和input 2.txt的文本文件提供，文件的第一行有 1 个正整数 n，表示石子的堆数。第二行有 n 个数，分别表示每堆石子的个数。
3、硬、软件环境
计算机型号：Windows 11版81FW
编程语言：C++
开发工具：Dev-C++
4、实验预备工作
设计思想：
与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，不同的是会保存已解决的子问题的答案，从而在需要时再找出已求得的答案，这样就可以避免大量重复的计算了。
适用条件：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）不满足分治策略的子问题相互独立的条件，也就是相邻子问题并不是相互独立的，而是相互有联系的；
（4）利用该问题分解出的子问题的解可以合并为该问题的解；
基本要素：
问题可被分解；具有最优子结构；子问题不是相互独立的；
解题步骤：
（1）最优子结构性质：找出最优解的性质，并刻划其结构特征。
（2）建立递归关系：递归地定义最优值。
（3）计算最优值：以自底向上的方式计算出最优值。
（4）构造最优解：根据计算最优值时得到的信息，构造最优解。
二、实验报告
1、实验步骤
问题1：
问题分析：要求出租站1到出租站n的所需要的最少租金，我们可以将问题变成
求出租站1到出租站i所需要的租金加上出租站i到出租站n的租金之和最少的问题，然后对出租站1到出租站i，和出租站i到出租站n再用同样的方法进行拆分，直到拆分到不可再分为止。
设计思想：用一个数组min_r[j]来储存第一站到第j站的最小租金，初始值为出租站1直接到出租站j的租金（1 < j <= n）。明显出租站1到出租站1的min_r[1]=0；出租站1到出租站2不可分，所以min_r[2]=r[1][2];从出租站3及以后的出租站i，min_r[i]=min（min_r[j]+r[j][i],其中 1 < j < i ）。
算法描述：
问题1：
问题分析：求n堆合并得分最小也就是求n-1堆的最小得分加剩下的那一堆的分数；而n-1堆石子的最小得分又可分成n-2堆的最小得分和剩下一堆的分数；……一直分到n-(n-2)小堆石子“合并”加剩下另一堆的分数。
设计思想：设二维数组sum[i][j]表示第i堆石头到第j堆石子的总和，二维数组dp[i][j]表示从第i堆到第j堆石头合并的最小得分数，当只有一堆石子“合并”时(i = j)，最小得分就是该小堆石子的数量，dp[i][j]=0；当相邻两堆合并时，最小得分也只有一种情况，dp[i][j]=0+sum[i][j]；当三堆及以上合并时，dp[i][j]= min( dp[i][k]+dp[k+1][j]+sum[i][j],其中i< k <j)。
算法描述：
2、实验结果
问题1：
#include<iostream>
using namespace std;
int r[200][200];
int main(){
int n;
cin>>n;
int min_r[200];
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
cin>>r[i][j];
}
}
min_r[1]=0;
for(int j=2;j<=n;j++){
min_r[j]=r[1][j];
}
for(int i=3;i<=n;i++){
for(int j=1;j<i;j++){
if(min_r[i]>min_r[j]+r[j][i]){
min_r[i]=min_r[j]+r[j][i];
}
}
}
cout<<min_r[n]<<endl;
}
问题2：
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int aa[n],sum[n][n],dp[n][n];
for (int i=0; i<n; i++) {
cin>>aa[i];
}
for (int i=0;i<n;i++) {
for (int j=i;j<n;j++) {
dp[i][j]=999999;
if (i==j)
sum[i][j]=aa[i];
else
sum[i][j]=sum[i][j-1]+aa[j];
}
}
for (int i=0;i<n;i++) {
dp[i][i]=0;
if (i<n-1)
dp[i][i+1]=sum[i][i+1];
}
for(int i=0;i<n-1;i++){
for(int j=i+2;j<n;j++){
for(int k=i;k<=j;k++)
if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[i][j]){
dp[i][j]=dp[i][k]+dp[k+1][j]+sum[i][j];
}
}
}
cout<<"最小得分："<<dp[0][n-1]<<endl;
}
3、实验结论
……………………（懒）……………………