溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
題目：數字三角形
題目介紹：如圖所示的數字三角形，要求從最上方頂點開始一步一步下到最底層，每一步必須下一層，求出所經過的數字的最大和。
輸入：第一行值n，代表n行數值；后面的n行數據代表每一行的數字。
輸出：經過數字的最大和。
例：
輸入：
4
1
3 2
4 10 1
4 3 2 20
輸出：
24
分析：這也是一個典型的貪心算法無法解決的問題，同樣可以用動態規劃（dp算法）來解決。把邊界數字首先初始化到結果矩陣中，再根據狀態方程完成結果矩陣的遍歷。需要注意的就是數組不是矩形而是三角形，與傳統的狀態方程相比需要做點改進。
數組編號：
狀態方程：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;
}
}
結果如下圖：
所以最下層的數字和最大值是24.
總結
以上所述是小編給大家介紹的C++數字三角形問題與dp算法，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
