C++數(shù)字三角形問題與dp算法
更新時間：2018年09月02日 08:17:09 作者：會武術(shù)之白貓
這篇文章主要介紹了C++數(shù)字三角形問題與dp算法的相關(guān)知識，非常不錯，具有一定的參考借鑒價值 ,需要的朋友可以參考下
題目：數(shù)字三角形
題目介紹：如圖所示的數(shù)字三角形，要求從最上方頂點開始一步一步下到最底層，每一步必須下一層，求出所經(jīng)過的數(shù)字的最大和。
輸入：第一行值n，代表n行數(shù)值；后面的n行數(shù)據(jù)代表每一行的數(shù)字。
輸出：經(jīng)過數(shù)字的最大和。
例：
輸入：
4
1
3 2
4 10 1
4 3 2 20
輸出：
24
分析：這也是一個典型的貪心算法無法解決的問題，同樣可以用動態(tài)規(guī)劃（dp算法）來解決。把邊界數(shù)字首先初始化到結(jié)果矩陣中，再根據(jù)狀態(tài)方程完成結(jié)果矩陣的遍歷。需要注意的就是數(shù)組不是矩形而是三角形，與傳統(tǒng)的狀態(tài)方程相比需要做點改進(jìn)。
數(shù)組編號：
狀態(tài)方程：p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]}
代碼如下：
#include <iostream>
using namespace std;
int main()
{
int i;
int n;
cin >> n;
int **p = new int *[n];
for (i = 0; i < n; i++)
{
p[i] = new int[n];
}
for (i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
cin >> p[i][j];
}
}
for (i = 1; i < n; i++)
{
p[i][0] += p[i - 1][0];
}
for (i = 1; i < n; i++)
{
p[i][i] += p[i - 1][i - 1];
}
for (i = 2; i < n; i++)
{
for (int j = 1; j < i; j++)
{
p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j];
}
}
for (i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
cout << p[i][j] << " ";
}
cout << endl;
}
}
結(jié)果如下圖：
所以最下層的數(shù)字和最大值是24.
總結(jié)
以上所述是小編給大家介紹的C++數(shù)字三角形問題與dp算法，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復(fù)大家的！
相關(guān)文章
這篇文章主要介紹了實現(xiàn)二叉樹的創(chuàng)建（先序）、遞歸及非遞歸的先、中、后序遍歷2013-11-11
這篇文章主要為大家詳細(xì)介紹了C++17中if和switch語句的新特性的相關(guān)知識,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-12-12
本文主要對比了C語言中的兩個函數(shù)perror和fprintf的區(qū)別,perror主要用于輸出與系統(tǒng)錯誤相關(guān)的消息,根據(jù)全局變量errno的值生成錯誤信息,而fprintf則用于格式化輸出任意類型的信息到指定的文件流2024-10-10
這篇文章主要介紹了C語言中正切的相關(guān)函數(shù)總結(jié),包括正切和反正切以及雙曲線正切等的函數(shù),需要的朋友可以參考下2015-08-08
C++中string與int的相互轉(zhuǎn)換實現(xiàn)代碼
這篇文章主要介紹了C++中string與int的相互轉(zhuǎn)換實現(xiàn)代碼,需要的朋友可以參考下2017-05-05
本篇文章是對shell排序的實現(xiàn)代碼進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
線段樹在一些acm題目中經(jīng)常見到,這種數(shù)據(jù)結(jié)構(gòu)主要應(yīng)用在計算幾何和地理信息系統(tǒng)中,這篇文章主要給大家介紹了關(guān)于線段樹以及C++實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語言判斷一個數(shù)是否為素數(shù)方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了c++中std::hash以及萬能hash的使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
C語言實現(xiàn)航空訂票系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)航空訂票系統(tǒng)課程設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03