寧波制作網(wǎng)站公司廣告外鏈購買交易平臺(tái)
題目描述
數(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;
}