數字三角形問題
1.題目描述：給定一個由n行數字組成的數字三角形，如圖3-7所示。設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。
算法設計:對于給定的由n行數字組成的數字三角形，計算從三角形的頂至底的路徑經過的數字和的最大值。

#include<iostream> using namespace std;int Numeric_triangle(int **vector,int n,int **temp) {for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){temp[i][j] = vector[i][j];}}for(int i=n-1;i>=1;i--)//從倒數第二行開始往上遞推{for(int j=1;j<=n;j++){if(temp[i+1][j]>temp[i+1][j+1])//將每個數下面的兩個數進行比較temp[i][j]=temp[i][j]+temp[i+1][j]; //取較大的數加 elsetemp[i][j]=temp[i][j]+temp[i+1][j+1];}}return temp[1][1];}int main() {int n;cout<<"輸入數字三角形的高度";cin>>n;int **vector = new int *[n];for(int i=1;i<=n;i++){vector[i] = new int [n];}int **temp = new int *[n];for(int i=1;i<=n;i++){temp[i] = new int [n];}cout<<"輸入數字三角形"<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>vector[i][j];}}cout<<"路徑的最大和為："<<Numeric_triangle(vector,n,temp)<<endl;cout<<"自頂向下的路徑為:";cout<<" "<<vector[1][1]<<" ";int col=1;for(int i=2;i<=n;i++){if(temp[i][col]>temp[i][col+1]){cout<<vector[i][col]<<" ";} else{cout<<vector[i][col+1]<<" ";col++;}}return 0;}

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法设计与分析——动态规划——数字三角形问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。