hihocoder1037（记忆化搜索）

编码之夜

于 2015-04-02 21:06:20 发布

阅读量784

点赞数

分类专栏： Hiho 文章标签： dp

本文链接：https://blog.csdn.net/u013447865/article/details/44837421

版权

Hiho 专栏收录该内容

9 篇文章

订阅专栏

本文介绍了一种使用记忆化搜索解决数字三角形问题的方法，通过动态规划推导出转移方程，实现了高效的求解最大路径和的算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目连接：点击打开链接

解题思路：

和白书上的数字三角形一样，用记忆化搜索解决，推出转移方程dp[i][j] = g[i][j] + max( d( i + 1 , j ) , d( i + 1 , j + 1) );

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;
const int maxn = 1111;
int g[maxn][maxn];
int dp[maxn][maxn];
int n;
int d(int i , int j)
{
    if(dp[i][j] > 0)    return dp[i][j];
    return dp[i][j] = g[i][j] + (i == n ? 0 : max(d(i + 1 , j) , d(i + 1 , j + 1)));
}

int main()
{
    #ifdef DoubleQ
    freopen("in.txt" , "r" , stdin);
    #endif
    while(cin >> n)
    {
        memset(g , 0 , sizeof(g));
        memset(dp , -1 , sizeof(dp));
        for(int i = 1 ; i <= n ; i ++)
        {
            for(int j = 1 ; j <= i ; j ++)
            {
                cin >> g[i][j];
            }
        }
        cout << d(1 , 1) << endl;
    }
}