NOIP2012普及组初赛 阅读程序 第3题 《数字三角形》

Keywords: 递归，递推，顺推，逆推

分析：

阅读程序，我们从main函数入手，

输入的三角形，存入到a[i]数组里，从solve(1,1)左上角的数字进行递归调用

拿代码分析一下

#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

int n, i, j, a[100][100];

int solve(int x, int y)
{
    if (x == n) return a[x][y];  //递归边界

    int u = solve(x + 1, y);     //向下走 
    int v = solve(x + 1, y + 1); //向右下走 

    return max(a[x][y] + u, a[x][y] + v); //哪个路径上的值大，返回哪个 

}

int main()
{
    freopen("sanjiaoxing.in", "r", stdin);
    cin >> n;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            cin >> a[i][j];

    cout << solve(1, 1) <<endl;  //最后返回的是，所有路径当中，值最大的 

    return 0;
} 

好，这是我们从代码上能够分析出，这个递归调用的过程了。但是，现在要求的是初赛，要求人脑模拟手算。用递归的话，我们的脑子就要爆栈了。模拟起来也比较费力气。

所以，我们逆向思维。题目是从顶点往下走。我们可不可以从下往上走，逆推这个过程。

正推，红色路径的值为13，绿色路径的值为14

逆推，得到最大值，14。

显然，逆推的方更适合手算和正推适合验证。