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

心已赠人 2022-11-07 04:06 178阅读 0赞

# 题目要求 #

[题目链接][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NjMxOA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NjMxOA_size_16_color_FFFFFF_t_70 1]

# 分析 #

应该用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 <iostream>
    #include <cmath>
    
    using namespace std;
    
    int nums[1001][1001], result[1001][1001];
    
    int main() {
        
        int r;
        cin >> r;
        for (int i = 0; i < r; i++) {
        
            for (int j = 0; j <= i; j++) {
        
                cin >> nums[i][j];
            }
        }
        for (int i = r-1; i >= 0; i--) {
        
            for (int j = 0; j <= i; j++) {
        
                result[i][j] = max(result[i+1][j+1], result[i+1][j]) + nums[i][j];
            }
        }
        cout << result[0][0];
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1216
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NjMxOA_size_16_color_FFFFFF_t_70]: /images/20221023/2c812a159c2c44f3b8fc5f87cd32b1a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NjMxOA_size_16_color_FFFFFF_t_70 1]: /images/20221023/00d34e209d6a46969e8f1447b2e62867.png