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)方程相比需要做點改進。
數(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)文章
C語言中的char是用于聲明單個字符的關(guān)鍵字,這篇文章主要給大家介紹了關(guān)于C語言char類型中存儲的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-01-01
項目之C++如何實現(xiàn)數(shù)據(jù)庫連接池
這篇文章主要介紹了項目之C++如何實現(xiàn)數(shù)據(jù)庫連接池問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
七夕節(jié)還不知道送啥，教你用MATLAB制作一款刮刮樂抽獎特效，讓她的手氣決定她的禮物。文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2022-03-03
本篇文章是對使用C語言實現(xiàn)CRC校驗的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
C++實現(xiàn)字符串元音字母反轉(zhuǎn)的兩種方法
在處理字符串問題時,我們經(jīng)常需要對其中的字符進行操作,例如反轉(zhuǎn)、替換等,本文將詳細討論如何在C++中實現(xiàn)僅反轉(zhuǎn)字符串中的所有元音字母,并返回結(jié)果字符串,需要的朋友可以參考下2024-07-07
本文主要介紹了Qt編譯OpenCV的實現(xiàn)步驟,通過詳細的步驟和說明,幫助開發(fā)者在Qt環(huán)境中成功集成并編譯OpenCV,從而為各類計算機視覺項目提供強大的支持,感興趣的可以了解一下2024-01-01
本文介紹了C語言中幾個常用的內(nèi)存函數(shù),包括memcpy、memmove、memset、memcmp的使用方法及其模擬實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-11-11
這篇文章主要為大家詳細介紹了C++實現(xiàn)二分法求方程近似解，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
C語言中g(shù)etch()函數(shù)詳解及簡單實例
這篇文章主要介紹了C語言中g(shù)etch()函數(shù)詳解及簡單實例的相關(guān)資料,需要的朋友可以參考下2017-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)快速排序的改進代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-08-08