898. 数字三角形（线性dp模版1

题源动态规划经典题源1把大问题转变为一个个子问题从子问题得到最优子结构向大问题递推—下一阶段的最优解应该能够从当前阶段的子问题的最优解中导出被称为最优子结构性质。切当前已求解的子问题不受后序阶段的影响这个条件被称为无后效性。易得一个最小的数塔是从二层开始的得到二层数塔可以递推到三层数塔为满足无后效性和最优子结构从数塔的底层向上递推。#includebits/stdc.husingnamespacestd;constintN1000;intarr[N][N];intdp[N][N];intmain(){intn;cinn;for(inti1;in;i){for(intj1;ji;j){cinarr[i][j];}}for(intin;i1;i--){for(intj1;ji;j){dp[i][j]arr[i][j]max(dp[i1][j],dp[i1][j1]);}}coutdp[1][1];return0;}