普通递归算法：

int NumberTrangle(int trang[][100], int i, int j, int numOfLine)　　　　//numOfLine即三角形的高度

{

    if(i == numOfLine)

        return trang[i][j];　　　　最低层的不用计算。

    else

        return trang[i][j] + std::max(NumberTrangle(trang, i+1, j, numOfLine), NumberTrangle(trang, i+1, j+1, numOfLine));

}

 

自底向上递推算法：

int NumberTrangle(int trang[][100], int util[][100], int height)

{

    for(int j = 0; j < height; ++j)

    {

        util[height - 1][j] = trang[height - 1][j];

    }

    for(int i = height - 2; i >= 0; --i)

    {

        for(int j = 0; j <= i; ++j)

        {

            util[i][j] = trang[i][j] + std::max(util[i+1][j], util[i+1][j+1]);

        }

    }

    return util[0][0];

}

记忆化算法：

int NumberTrangle(int trang[][100], int util[][100], int i, int j, int numOfLine)

{

    if(util[i][j] > 0)

        return util[i][j];

    if(i == numOfLine)

        return util[i][j] = trang[i][j];

    else

        return util[i][j] = trang[i][j] + std::max(NumberTrangle(trang, util, i+1, j, numOfLine), NumberTrangle(trang, util, i+1, j+1, numOfLine));

}