首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。