您好,登錄后才能下訂單哦!
題目:數(shù)字三角形
題目介紹:如圖所示的數(shù)字三角形,要求從最上方頂點(diǎn)開(kāi)始一步一步下到最底層,每一步必須下一層,求出所經(jīng)過(guò)的數(shù)字的最大和。
輸入:第一行值n,代表n行數(shù)值;后面的n行數(shù)據(jù)代表每一行的數(shù)字。
輸出:經(jīng)過(guò)數(shù)字的最大和。
例:
輸入:
4
1
3 2
4 10 1
4 3 2 20
輸出:
24
分析:這也是一個(gè)典型的貪心算法無(wú)法解決的問(wèn)題,同樣可以用動(dòng)態(tài)規(guī)劃(dp算法)來(lái)解決。把邊界數(shù)字首先初始化到結(jié)果矩陣中,再根據(jù)狀態(tài)方程完成結(jié)果矩陣的遍歷。需要注意的就是數(shù)組不是矩形而是三角形,與傳統(tǒng)的狀態(tài)方程相比需要做點(diǎn)改進(jìn)。
數(shù)組編號(hào):
狀態(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ù)字三角形問(wèn)題與dp算法,希望對(duì)大家有所幫助,如果大家有任何疑問(wèn)歡迎給我留言,小編會(huì)及時(shí)回復(fù)大家的!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。