首页 > 代码库 > SDUT-1730

SDUT-1730

/********************************************************************* @file     Main_practise.cpp* @date     2014-9-21* @author   Tiger* @brief    数字三角形问题* @details  动态规划-记忆化搜索********************************************************************/#include <cstdio>#include <algorithm>const int MAX = 100;int Data[MAX][MAX];int Memo[MAX][MAX];int solve(int i, int j, int nNum);int main(int argc, const char* argv[]){    int nNumCnt = 0;    while (scanf("%d", &nNumCnt) != EOF)    {        for (int i=0; i<nNumCnt; ++i)        {            for (int j=0; j<=i; ++j)            {                scanf("%d", &Data[i][j]);                Memo[i][j] = -1;            }        }        printf("%d\n", solve(0, 0, nNumCnt));    }    return 0;}int solve(int i, int j, int nNum){    if (Memo[i][j] >= 0)    {        return Memo[i][j];    }    else    {        return Memo[i][j] = Data[i][j] + (i == nNum-1 ? 0 : std::max(solve(i+1, j, nNum),            solve(i+1, j+1, nNum)));    }}

 

SDUT-1730