第9章--第3节-动态规划经典题(C++版)PPT.ppt

第九章 动态规划; 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些有哪些信誉好的足球投注网站或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。;第四三节 动态规划经典题; s[i]表示前i堆石头的价值总和，f[i][j]表示把第i堆到第j堆的石头合并成一堆的最优值。 for (i=n-1;i=1;i--) for (j=i+1;j=n;j++) for (k=i;k= j-1;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); 输出f[1][n]; 【参考程序】 #includecstdio #includecstring int min(int a,int b) { return a b ? b:a; // 三目运算符，相当于if(ab) return b; else return a; } int f[101][101]; int s[101]; int n,i,j,k,x; int main() { scanf(%d,n); for (i=1; i=n; i++) { scanf(%d,x); s[i]=s[i-1]+x; } memset(f,127/3,sizeof(f)); //赋值127是很大的正数，若无/3后面的相加 for (i=1; i=n; i++) f[i][i]=0; //可能超出int的范围 for (i=n-1; i=1; i--) for (j=i+1; j=n; j++) for (k=i; k=j-1; k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); printf(%d\n,f[1][n]); return 0; };【参考程序】 #includecstdio long long a[11][11],f[11][11]; long long s; int n,i,k,k1,j; int max(int a, int b) { return ab?a:b; } int main() { scanf(%d%d,n,k1); scanf(%lld,s); for (i=n; i=1; i--) { a[i][i]=s%10; s/=10; } for (i=2; i=n; i++) for (j=i-1;j=1;j--) a[j][i]=a[j][i-1]*10+a[i][i]; ; for (i=1; i=n; i++) //预处理不加乘号的情况 f[i][0]=a[1][i]; for (k=1; k=k1; k++) for (i=k+1; i=n; i++) for (j=k; ji; j++) f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]); printf(%lld\n,f[n][k1]); return 0; } ;【例9-20】编辑距离 【问题描述】 设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2、插入一个字符； 3、将一个字符改为另一个字符。 【编程任务】 对任的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。 【输入格式】edit.in 第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。 【输出格式】edit.out 只有一个正整数，为最少字符操作次数。 【输入样例】 sfdqxbw gfdgw 【输出样例】 4 【算法分析】 状态：f[i][j]记录ai与bj