计算机算法设计与分析 第三章 动态规划 上机题
7-1 数字三角形 (30 分)
1.题目描述
给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。
输入格式:
输入有n+1行：
第 1 行是数字三角形的行数 n，1<=n<=100。
接下来 n行是数字三角形各行中的数字。所有数字在0…99 之间。
输出格式:
输出最大路径的值。
输入样例:
在这里给出一组输入。例如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
在这里给出相应的输出。例如：
30
2.基本思路
一篇写的很清楚的博客
不断优化时间与空间复杂度
3.参考代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+1][n+1];
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
cin>>a[i][j];
}
}
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<n;j++)
// {
// cout<<a[i][j]<<" ";
// }
// cout<<endl;
// }
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
}
}
cout<<a[0][0];
}
7-2 最大子段和 (40 分)
1.题目描述
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。
要求算法的时间复杂度为O(n)。
输入格式:
输入有两行：
第一行是n值（1<=n<=10000)；
第二行是n个整数。
输出格式:
输出最大子段和。
输入样例:
在这里给出一组输入。例如：
6
-2 11 -4 13 -5 -2
输出样例:
在这里给出相应的输出。例如：
20
2.基本思路
S[i]:表示以a[i]为结尾的最大子序列和
3.参考代码
// // 思路：
// // S[i]:表示以a[i]为结尾的最大子序列和
// // S[i]={a[i] 若S[i-1]<=0
// // a[i]+S[i-1] 若S[i-1]>0
//法一：
// #include <iostream>
// using namespace std;
// int main()
// {
// int n;
// cin>>n;
// int a[n];
// for(int i=0;i<n;i++)
// {
// // cin>>a[i];
// scanf("%d",&a[i]);
// }
// int nowN=0;
// int maxN=0;
// for(int i=0;i<n;i++)
// {
// nowN+=a[i];
// if(nowN>maxN) maxN=nowN;
// if(nowN<0) nowN=0;
// }
// printf("%d",maxN);
// }
// 按书上的动态规划算法
#include <iostream>
using namespace std;
int MaxSum(int n,int *a){
int sum=0,b=0;
for(int i=1;i<n;i++){
if(b>0){
b+=a[i];
}
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
cout<<MaxSum(n,a);
}
7-3 编辑距离问题 (30 分)
1.题目描述
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。
输入格式:
第一行是字符串A，文件的第二行是字符串B。
提示：字符串长度不超过2000个字符。
输出格式:
输出编辑距离d(A,B)
输入样例:
在这里给出一组输入。例如：
fxpimu
xwrs
结尾无空行
输出样例:
在这里给出相应的输出。例如：
5
结尾无空行
2.基本思路
3.参考代码
#include <iostream>
#include <string.h>
using namespace std;
//1、初始化：当strlen(a)=0,res[0][j]=j;同理可得res[i][0]=i;
//
//2、当a[i-1]=b[j-1],则res[i][j]=res[i-1][j-1]，即等于左上角的元素;
//
//3、当a[i-1]!=b[j-1]，有以下三种情况：
//
//（1）若进行删除操作：操作数加1，res[i][j]=res[i-1][j]+1;
//
//（2）若进行增加操作：操作数加1，res[i][j]=res[i][j-1]+1;
//
//（3）若进行替换操作：操作数加1，res[i][j]=res[i-1][j-1]+1;
//
// res[i][j]等于上面三种情况res[i][j]里的最小值
//
//通过以上分析，我们可以发现填表规则是从上到下从左往右填一个大小为strlen(a)*strlen(b)的表格，两层for循环对res数组操作：匹配时取左上的值；
//
//失配时取 左上+1，左边+1，右边+1 三个数中的最小值，更新res[i]][j];
//
//最后递推到右下角dp[la][lb]为所求答案
//详见blog
int minN(int a,int b,int c)
{
return ((a>b)?b:a)>c?c:((a>b)?b:a);
}
int main()
{
// cout<<minN(342,4647,341)<<endl;
string a,b;
cin>>a;
cin>>b;
int la=a.length();
int lb=b.length();
int res[la+1][lb+1]={0};
for(int i=0;i<=la;i++)
{
res[i][0]=i;
}
for(int i=0;i<=lb;i++)
{
res[0][i]=i;
}
// for(int i=0;i<=la;i++)
// {
// for(int j=0;j<=lb;j++)
// {
// cout<<res[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
for(int i=1;i<=la;i++)
{
for(int j=1;j<=lb;j++)
{
if(a[i-1]==b[j-1]) res[i][j]=res[i-1][j-1];
else{
res[i][j]=minN(res[i-1][j-1]+1,res[i-1][j]+1,res[i][j-1]+1);
// cout<<res[i][j]<<endl;
}
}
// for(int i=0;i<=la;i++)
// {
// for(int j=0;j<=lb;j++)
// {
// cout<<res[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
}
cout<<res[la][lb];
}