为什么 memoization 会给出错误的输出？

Question

我正在尝试使用递归+记忆来解决问题。它只是修改后的斐波那契数列，增加了一个只能完成 K 次的 start+3 步。这是我想出的递归代码：

#include <iostream>
using namespace std;

int helper(int start, int N, int K) {
    // cout<<start<<" "<<N<<" "<<K<<"\n";
    if(start>N) return 0;
    if(start==N) return 1;
    
    int ans=0;
    ans=helper(start+1, N, K) + helper(start+2, N, K);
    if(K>0) {
        K--;
        ans=ans+helper(start+3, N, K);
    }
    
    return ans;
}

int main() {
    int T;
    cin>>T;
    while(T--) {
        int N, K;
        cin>>N>>K;
        cout<<helper(0, N, K)<<"\n";
    
    }
    
    return 0;
}

只是记住它并取模 10^9+7（问题需要我做），我有：

#include <iostream>
#include <vector>
using namespace std;

vector<long long int> dp;
const unsigned int M = 1000000007;

int helper(long long int start, long long int N, int K) {
    // cout<<start<<" "<<N<<" "<<K<<"\n";
    if(start>N) return 0;
    if(start==N) return 1;
    if(dp[start]!=0) {
        return dp[start];
    }
    
    int ans=0;
    ans=(helper(start+1, N, K)%M + helper(start+2, N, K)%M)%M;
    if(K>0) {
        K--;
        ans=(ans%M+helper(start+3, N, K)%M)%M;
    }
    
    return dp[start]=ans;
}

int main() {
    int T;
    cin>>T;
    while(T--) {
        long long int N;
        int K;
        cin>>N>>K;
        dp.clear();
        dp.resize(N+5, 0);
        cout<<helper(0, N, K)<<"\n";
    }
    
    return 0;
}

代码完全相同，但用于记忆和取模。当我运行它在以下输入上时：

1
7 1

我在第一种情况下得到 41，而在第二种情况下得到 44。显然，我进行了调试，我预计会出现一些记忆或取模问题。但是，我注意到一些评估不再被计算，由此我得出了递归调用的一些问题。请注意调用的差异 here and working code snippets here and here.

有人可以指出我遗漏了什么吗？

Answer 1

您在 db 中缓存完全基于 start 的结果，并完全忽略 K。但是 helper(0, 7, 0) 和 helper(0,7,7) 需要根据剩余的 K 在每个索引处缓存完全不同的数字。所以你需要缓存 index 也基于 K.

我看到三种优化方式：

有缓存的缓存。 db[start] 将是 std::vector，您将在该向量中使用索引 K 来访问您的项目。这会导致使用更多的内存。
放弃 std::vector 并使用 std::unordered_map，其中您的密钥是一对 (start, K)。（可能 std::pair<int, int>，但最好使用具有更好名称的结构。）这应该使用更少的内存，并且几乎没有速度损失。
仅在 K==0 时缓存值。这不会增加您的缓存大小，但是当 K 很大时您也会失去很多缓存优势。

为什么 memoization 会给出错误的输出？

Why is memoization giving the wrong output?

c++

algorithm

recursion

memoization