数字三角形（洛谷P1216题题解，C++语言描述）

题目要求

题目链接

分析

应该用DP来解，对于题给三角形，我们可以这么看：

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

从上到下坐标x递增，从左到右坐标y递增。

我们要求的是全局最优解，每个位置只可能到它下一层的同坐标y或y+1，这样就可以从下向上递推，写出状态转移方程： r e s u l t [ i ] [ j ] = m a x ( r e s u l t [ i + 1 ] [ j + 1 ] , r e s u l t [ i + 1 ] [ j ] ) + n u m s [ i ] [ j ] result[i][j] = max(result[i+1][j+1], result[i+1][j]) + nums[i][j] result[i][j]=max(result[i+1][j+1],result[i+1][j])+nums[i][j]。

然后循环遍历即可求解，注意 i i i和 j j j的循环方向。

AC代码

#include 
#include 

using namespace std;

int nums[1001][1001], result[1001][1001];

int main() {
    int r;
    cin >> r;
    for (int i = 0; i  nums[i][j];
        }
    }
    for (int i = r-1; i >= 0; i--) {
        for (int j = 0; j