題目要求
提示：頭歌 算法作業(yè) 實驗七 動態(tài)規(guī)劃 第1關：數(shù)塔問題
本關任務：編寫用動態(tài)規(guī)劃解決數(shù)塔問題。
一、解題關鍵要點（頭歌題目已經(jīng)給）
二、解題過程
1.關于數(shù)塔問題的動態(tài)規(guī)劃過程自分析【重點】
求解過程（自底向上）
決策結果輸出過程（自頂向下）
將上述分析求解過程角標記錄為path數(shù)組 ,方便順序輸出結果
2.解題代碼
代碼如下（不知題目給出三維數(shù)組的a的第三維我用處，去除）：
#include <stdio.h>
#define N 5 //問題規(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++) //初始子問題 ，倒數(shù)第二層（第i-1層）開始
dp[N][j] = a[N][j];
for (i = N - 1; i >= 1; i--) //進行第 i+1 層的決策，從i 到 1 向上
for (j = 1; j <= i+1; j++) { //每一層有 i+1 個
if (dp[i + 1][j] > dp[i + 1][j + 1]) {
dp[i][j] = a[i][j] + dp[i + 1][j];
path[i][j] = j; //本次決策選擇下標j的元素
}
else {
dp[i][j] = a[i][j] + dp[i + 1][j + 1];
path[i][j] = j + 1; //本次決策選擇下標j+1的元素
}
}
printf("max=%d\n", dp[1][1]);
printf("數(shù)值和最大的路徑是：");
j = path[1][1]; //計算dp[1][1]的選擇
for (i = 1; i < N; i++)
{
printf("%d->", a[i][j]);
j = path[i][j]; //計算dp[i][j]的選擇
}
printf("%d\n", a[i][j]);
}
3.運行結果
文章來源：http://www.zghlxwxcb.cn/news/detail-513395.html
總結
上課沒好好聽這塊??????，到做題了，瞎揣一氣，望指正??文章來源地址http://www.zghlxwxcb.cn/news/detail-513395.html
到了這里，關于【算法設計與分析】動態(tài)規(guī)劃：數(shù)塔問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
