将记忆（dp）添加到我的递归代码中会给出不同的结果，这是错误的

Question

我已经被 dp 问题困扰了好几个星期了，无法想出我做错了什么。问题链接如下：

网格中递增路径的数量：

https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/

问题陈述的结论是，给定一个整数网格（二维矩阵），您必须返回总的唯一递增路径，递增路径定义为从较小的数字移动到严格递增的数字，例如：2->3 ->5.

我用简单的递归解决了这个问题，它在最后几种情况下给出了正确的结果和TLE，但是当我添加 2 个基本行 dp 时，它在每个要转换为 dp 的递归代码中使用，但是当我在这个问题中这样做时，它给出了错误的结果。

代码：

class Solution {
public:
    int solve(vector<vector<int>>& dp,vector<vector<int>>& grid,int i,int j,int count){
        // if(dp[i][j]!=-1)
        //     return dp[i][j];
        if((i+1)<grid.size() && grid[i+1][j]>grid[i][j])
            count=1+solve(dp,grid,i+1,j,count);
        if((j+1)<grid[0].size() && grid[i][j+1]>grid[i][j])
            count=1+solve(dp,grid,i,j+1,count);
        if((i-1)>=0 && grid[i-1][j]>grid[i][j])
            count=1+solve(dp,grid,i-1,j,count);
        if((j-1)>=0 && grid[i][j-1]>grid[i][j])
            count=1+solve(dp,grid,i,j-1,count);
        return dp[i][j]=count;
    }
    int countPaths(vector<vector<int>>& grid) {
        long long ans=0;
        vector<vector<int>>dp(grid.size()+1,vector<int>(grid[0].size()+1,-1));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                ans=ans+solve(dp,grid,i,j,1);
            }
        }
        return ans%1000000007;
    }
};

当我删除这些评论时，它会给出错误的结果。我认为我错过了一些重要的概念，因为这是我第二次面临此类问题。

Answer 1

问题是你的

count

是累积，所以它不能用于记忆。这样的计数包括所有先前遍历通过网格的结果，并且不代表特定于给定坐标对的计数。

因此，如果某个单元格在此过程中被访问得很晚（例如当它位于右下角时），计数将不会从 1 开始，因为它已经计算了许多不涉及该新单元格的其他路径。现在，该计数中添加了从此新单元格中开始的路径，但结果本身并不代表该单元格，因此，如果在第二次访问时您从记忆中返回该计数，则您将重复计算许多不相关的路径.

解决方案是使用local计数：每次从某个单元格开始时从 0 开始计数。这些独立计数的总和仍然是您的答案，但现在您可以使用计数进行记忆。

不相关，但您的代码还有另一个问题：对于较大的输入，您将超出

long long

变量的

count

容量。您应该重复应用模运算符，以使计数保持在界限内。

如果您无法使其工作，这里是对您的代码的更正作为剧透：

class Solution {
 public:
     int solve(vector<vector>& dp,vector<vector>& grid,int i,int j){
         if(dp[i][j]!=-1) {
             return dp[i][j];
         }
         int count = 1;
         if((i+1)<grid.size() && grid[i+1][j]>grid[i][j])
             count += solve(dp,grid,i+1,j);
         if((j+1)<grid[0].size() && grid[i][j+1]>grid[i][j])
             count += solve(dp,grid,i,j+1);
         if((i-1)>=0 && grid[i-1][j]>grid[i][j])
             count += solve(dp,grid,i-1,j);
         if((j-1)>=0 && grid[i][j-1]>grid[i][j])
             count += solve(dp,grid,i,j-1);
         return dp[i][j] = count % 1000000007;
     }
     int countPaths(vector<vector>& grid) {
         int ans=0;
         vector<vector>dp(grid.size()+1,vector(grid[0].size()+1,-1));
         for(int i=0;i<grid.size();i++){
             for(int j=0;j<grid[0].size();j++){
                 ans = (ans + solve(dp,grid,i,j)) % 1000000007;
             }
         }
         return ans;
     }
 };