首页 > 代码库 > 数字三角形
数字三角形
普通递归算法:
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));
}
数字三角形