題目描述

數(shù)字三角形

輸入輸出樣例

輸入樣例#1：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

輸出樣例#1：

30

思路：

這題可能看到的第一眼——直接貪心然后一層一層判斷呀！！！不過很快又會(huì)發(fā)現(xiàn)，額___好像不行。因?yàn)榭赡墚?dāng)前選的是一個(gè)大的，但是后面全都是小的！！！
所以這時(shí)我們就需要用到動(dòng)態(tài)規(guī)劃了
動(dòng)態(tài)規(guī)劃基礎(chǔ)知識(shí)詳見： 動(dòng)態(tài)規(guī)劃基礎(chǔ)（超詳細(xì)）

這題我們從上到下行不通，那我們就要思考從下到上進(jìn)行操作

首先需要知道狀態(tài)轉(zhuǎn)移方程：
從圖中可知當(dāng)前這這個(gè)可以由左下角的數(shù)與右下角的數(shù)的最大值加上自己本來的數(shù)
所以狀態(tài)轉(zhuǎn)移方程為：

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];

然后我們需要知道DP的初值，那這題很明顯，就是輸入的最后一行，也就是：

for(int i=1;i<=n;i++) dp[n][i]=a[n][i];

AC代碼

最后呈上完整代碼：

#include<bits/stdc++.h>
using namespace std;
int n,a[101][101],dp[101][101];
int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) cin>>a[i][j];for(int i=1;i<=n;i++) dp[n][i]=a[n][i];for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];}}cout<<dp[1][1];return 0;
}