解决动态问题中的分段错误

Question

在动态问题中，这些类型的计算答案有什么不同吗？因为在代码 3 的情况下，我在代码 1 和代码 2 通过时遇到分段错误

int dp[8005][2];//dp is initialized as -1 in main
int a=4;
int b=6;
int tar=90;


int solve(int pos,int ba)
{
    
    if(pos<0||pos>8000||ba>=2)
        return 1e6+1;
    
    if(pos==tar)
        return 0;

    //Code 1
    int &ans=dp[pos][ba];
    if(ans!=-1)
       return dp[pos][ba];
    ans=1+solve(pos+a,0);
    ans=min(ans,1+solve(pos-b,ba+1));
    return ans;

    //Code 2
    if(dp[pos][ba]!=-1)
       return dp[pos][ba];
      dp[pos][ba]=1+solve(pos+a,0);
        dp[pos][ba]=min(dp[pos][ba],1+solve(pos-b,ba+1));
        return dp[pos][ba]; 
    
    //Code 3
  if(dp[pos][ba]!=-1)
       return dp[pos][ba];
   int ans=1+solve(pos+a,0);
    ans=min(ans,1+solve(pos-b,ba+1));
    return dp[pos][ba]=ans;
}

Answer 1

代码 3 不会更新 dp，直到 所有计算完成后。

前两个去

• 递归
• 更新dp
• 递归
• 更新dp
• Return 新值

请注意，1 和 2 是等价的，因为 ans 与 dp[pos][ba] 相同。

第三个是

• 递归
• 递归
• 更新 dp 和 return 新值