【前言】
今天是刷題打卡第62天！
記得加油哦，
原題：數字三角形（遞推、簡單DP）
原題鏈接：[USACO1.5][IOI1994]數字三角形 Number Triangles - 洛谷
題目描述：
輸入格式：
第一個行一個正整數 n ,表示行的數目，
后面每行為這個數字金字塔特定行包含的整數，
輸出格式：
單獨的一行,包含那個可能得到的最大的和，
資料范圍：
1 ≤ n ≤ 1000，三角形數字值在 [0,100] 范圍內，
示例:
輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 輸出：
30思路：
本題采用倒推的方式：
假設func[i][j]表示的是從 i, j 到最后一層的最大路徑之和
當從頂層沿某條路徑走到第i層向第i+1層前進時，我們的選擇是沿其下兩條可行路徑中最大數字的方向前進，所以找出遞推關系：func[i][j] += max(func[i+1][j],func[i+1][j+1])；
注意：func[i][j]表示當前數字的值，func[i+1][j]和func[i+1][j+1]分別表示從i+1,j、i+1,j+1到最后一層的最大路徑之和；
最終func[0][0]就是所求
代碼執行：
#include<stdio.h>
#include<algorithm>
using namespace std;
int func[1005][1005] = {0};
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int j = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j <= i; j++)
{
scanf("%d", &func[i][j]);
}
}
//假設func[i][j]表示的是從i, j到最后一層的最大路徑之和
//找出遞推關系：func[i][j]+=max(func[i+1][j],func[i+1][j+1]);
//func[i][j]表示當前數字的值，func[i+1][j]和func[i+1][j+1]分別表示從i+1,j、i+1,j+1到最后一層的最大路徑之和
//最終func[0][0]就是所求
for(i = n - 2; i >= 0; i--)
{
for(j = 0; j <= i; j++)
{
func[i][j] += max(func[i+1][j], func[i+1][j+1]);
}
}
printf("%d\n", func[0][0]);
return 0;
}結語
今天是刷題打卡第62天！
加油吧少年，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/385654.html
標籤：其他
下一篇：校尉羽書飛瀚海，順序表中增刪改