蓝桥，尝试递归加记忆化搜索，出现错误

Question

在梦境中，你踏上了一只木䇝，在江上漂流根据对当地的了解，你知道在你下游 D 米处有一个峡谷，如果你向下游前进大于等于 D 米则必死无疑。现在你打响了急救电话，T 秒后救援队会到达并将你救上岸。水流速度是 1 m/s，你现在有 M 点体力。每消耗一点体力，你可以划一秒桨使船向上游前 进 1m，否则会向下游前进 1 m (水流)。你有M 点体力需在救援队赶来前花光。因为江面太宽了，凭借你自己的力量不可能上岸。

请问，有多少种划桨的方案可以让你得救。

两个划桨方案不同是指：存在某一秒钟，一个方案划桨，另一个方案不划。

输入格式
输入一行包含三个整数
�
D，
�
T，
�
M。

输出格式
输出一个整数，表示可以让你得救的总方案数，答案可能很大，请输出方案数除以
1000000007
输入
1 6 3
输出
5

#include <iostream> 
int d,t,m;
int ans;
int dp[30][30];
int process(int cur,int step,int time)
{
    if(dp[time][step]!=-1)
    return dp[time][step];
    if(time==0||step<0||cur<0)
    {
        if(step==0&&cur>0)
        {
            ans++;
            ans=ans%1000000007;
        }
        return 0;
    }
    int p1=0,p2=0;
    if(cur-1>0)
    {
        p1=process(cur-1,step,time-1);
    }
    if(step>0)
    {
        p2=process(cur+1,step-1,time-1);
    }
    dp[time][step]=p1+p2;
    return p2+p1;
}
using namespace std;
int main()
{
    cin>>d>>t>>m;
    for(int i=0;i<30;i++)
    {
        for(int j=0;j<30;j++)
        {
            dp[i][j]=-1;
        }
    }
    process(d,m,t);
    cout<<ans;
    return 0;
}

我想试试用的递归加上记忆化搜索，但是代码好像出错了，输出的结果一直是一，请指教

Answer 1

参考通义千问和郭老师的小迷弟雅思莫了-编写提供，主要是为了帮助您快速解决问题，如下回答，您可以参考下，如有问题，评论区留言。

在您的代码中，我发现了几个问题。首先，您初始化 ans 变量为0，并且每次找到一个解时将其加1，然后对结果取模。但是在 process 函数递归调用过程中并没有正确累加结果到 ans 上。其次，在主函数中直接输出 ans 时，没有考虑到可能需要对结果取模。

针对以上问题，我对您的代码进行了修改：

#include <iostream>
using namespace std;

const int MOD = 1000000007;
int d, t, m;
int dp[30][30];

int process(int cur, int step, int time) {
    if (dp[time][step] != -1)
        return dp[time][step];
    
    if (time == 0 || step < 0 || cur < 0) {
        if (step == 0 && cur > 0)
            return 1; // 返回方案数为1，而不是累加到 ans 中
        else
            return 0;
    }

    int p1 = 0, p2 = 0;
    if (cur - 1 > 0)
        p1 = process(cur - 1, step, time - 1);
    if (step > 0)
        p2 = process(cur + 1, step - 1, time - 1);

    dp[time][step] = (p1 + p2) % MOD; // 在这里直接对结果取模
    return dp[time][step]; // 返回累计后的结果
}

int main() {
    cin >> d >> t >> m;
    for (int i = 0; i < 30; i++) {
        for (int j = 0; j < 30; j++) {
            dp[i][j] = -1;
        }
    }
    int result = process(d, m, t); // 获取最终结果
    cout << result << endl; // 输出结果
    return 0;
}

这样修改后，代码应该能正确计算并输出方案数了。同时注意，由于我们在计算过程中直接对结果取模，所以在返回和存储结果时都做了取模操作，因此最后不需要再额外对 result 取模。