本關(guān)任務(wù)：編寫(xiě)用動(dòng)態(tài)規(guī)劃解決數(shù)塔問(wèn)題。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：動(dòng)態(tài)規(guī)劃。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-475218.html
編程要求
求上圖從頂層到頂層的一個(gè)路徑，使路徑上的數(shù)字和最大。要求輸出最大的數(shù)字和max和數(shù)值和最大的路徑。
#include <stdio.h>
#define N 5 //問(wèn)題規(guī)模
int main() {
int a[50][50];
a[1][1] = 9;
a[2][1] = 12, a[2][2] = 15;
a[3][1] = 10, a[3][2] = 6, a[3][3] = 8;
a[4][1] = 2, a[4][2] = 18, a[4][3] = 9, a[4][4] = 5;
a[5][1] = 19, a[5][2] = 7, a[5][3] = 10, a[5][4] = 4, a[5][5] = 16;
int i, j, dp[50][50] = { 0 }, path[50][50] = { 0 };
for (j = 1; j <= N; j++) //初始子問(wèn)題 ，倒數(shù)第二層（第i-1層）開(kāi)始
dp[N][j] = a[N][j];
for (i = N - 1; i >= 1; i--) //進(jìn)行第 i+1 層的決策，從i 到 1 向上
for (j = 1; j <= i+1; j++) { //每一層有 i+1 個(gè)
if (dp[i + 1][j] > dp[i + 1][j + 1]) {
dp[i][j] = a[i][j] + dp[i + 1][j];
path[i][j] = j; //本次決策選擇下標(biāo)j的元素
}
else {
dp[i][j] = a[i][j] + dp[i + 1][j + 1];
path[i][j] = j + 1; //本次決策選擇下標(biāo)j+1的元素
}
}
printf("max=%d\n", dp[1][1]);
printf("數(shù)值和最大的路徑是：");
j = path[1][1]; //計(jì)算dp[1][1]的選擇
for (i = 1; i < N; i++)
{
printf("%d->", a[i][j]);
j = path[i][j]; //計(jì)算dp[i][j]的選擇
}
printf("%d\n", a[i][j]);
}
/********** End **********/?
本關(guān)任務(wù)：編寫(xiě)用動(dòng)態(tài)規(guī)劃解決最長(zhǎng)公共子序列問(wèn)題。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：動(dòng)態(tài)規(guī)劃。
編程要求
求字符串序列“ABCDBAB”和“BDCABA”的最長(zhǎng)公共子序列
#include <stdio.h>
#include <string.h>
int dp[100][100];
char a[100];
char b[100];
int maxm(int m,int n){
if(m>n) return m;
else return n;
}
int main(){
scanf("%s",a);
scanf("%s",b);
int m=strlen(a);
int n=strlen(b);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=maxm(dp[i-1][j],dp[i][j-1]);
}
}
}
//bnchdn
//chdn
printf("%d",dp[m][n]);
}
/********** End **********/本關(guān)任務(wù)：編寫(xiě)用動(dòng)態(tài)規(guī)劃解決最大子段和問(wèn)題。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：動(dòng)態(tài)規(guī)劃。
編程要求
給定由n個(gè)整數(shù)（可能為負(fù)數(shù)）組成的序列：a1,a2,……,an, 求該序列的最大子段和。當(dāng)所有整數(shù)均為負(fù)數(shù)，定義其最大子段和為0。
#include <stdio.h>
/********** Begin **********/
int main(){
int n;
scanf("%d",&n);
int a[n][2];
int max=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i][0]);
if(i==0){
a[i][1]=a[i][0];
}
else{
a[i][1]=a[i-1][1]+a[i][0]>a[i][0]?a[i-1][1]+a[i][0]:a[i][0];
}
max=max>a[i][1]?max:a[i][1];
}
printf("%d",max);
return 0;
}
/********** End **********/本關(guān)任務(wù)：編寫(xiě)用動(dòng)態(tài)規(guī)劃解決求最長(zhǎng)的單調(diào)遞增子序列長(zhǎng)度問(wèn)題。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：動(dòng)態(tài)規(guī)劃。
編程要求
給定一個(gè)長(zhǎng)度為n的數(shù)組，找出一個(gè)最長(zhǎng)的單調(diào)遞增子序列（不一定連續(xù)，但是順序不能亂）。例如：給定一個(gè)長(zhǎng)度為7的數(shù)組A5，6，7，1，2，8,9，則其最長(zhǎng)的單調(diào)遞增子序列為5，6，7，8，9，長(zhǎng)度為5。求318714101223411624的最長(zhǎng)的單調(diào)遞增子序列長(zhǎng)度。
#include <stdio.h>
/********** Begin **********/
int main(){
int n;
scanf("%d",&n);
int m[n][3];
m[0][1]=1;
m[0][2]=0;
for(int i=0;i<n;i++){
scanf("%d",&m[i][0]);
if(i!=0){
m[i][1]=0;
int k=i-1;
while(k>=0){
if(m[i][0]>m[k][0]){
if(k==i-1){
m[i][1]=m[k][1]+1;
m[i][2]=k;
}
else{
int max=m[k][1]+1;
if(max>m[i][1]){
m[i][1]=max;
m[i][2]=k;
}
}
}
k--;
}
if(k<0&&m[i][1]==0){
m[i][1]=1;
m[i][2]=i;
}
}
}
int max=m[0][1],j=0;
for(int i=0;i<n;i++){
if(m[i][1]>=max){
max=m[i][1];
j=i;
}
}
printf("%d\n",max);
}
/********** End **********/本關(guān)任務(wù)：編寫(xiě)用動(dòng)態(tài)規(guī)劃解決矩陣連乘問(wèn)題。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-475218.html
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：動(dòng)態(tài)規(guī)劃。
#include <stdio.h>
#include <stdlib.h>
/********** Begin **********/
int main(){
int n;
scanf("%d",&n);
int a[n][2];
int b[n][n]={0};
for(int i=0;i<n;i++){
scanf("%d %d",&a[i][0],&a[i][1]);
}
for(int i=1;i<n;i++){
for(int j=0;j<n-i;j++){
b[j][j+i]=b[j][j]+b[j+1][j+i]+a[j][0]*a[j][1]*a[j+i][1];
int k=j+1;
for(;k<j+i;k++){
int t=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1];
if(t<b[j][j+i]) {
b[j][j+i]=t;
}
}
}
}
printf("m[%d][%d]=%d",1,n,b[0][n-1]);
return 0;
}
/********** End **********/到了這里，關(guān)于頭歌實(shí)驗(yàn)七 動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
