动态编程问题-最小成本路径

Question

我正在尝试这个问题-Minimum Cost Path。我已经使用Dijkstra的最短路径算法解决了这个问题。但是当我使用递归+记忆化即动态编程尝试此操作时，我陷入了困境，无法调试我的代码。我需要有关我的代码错误的地方的帮助！

我很高兴获得帮助。

#include<bits/stdc++.h>

using namespace std;

int n;
int a[105][105], dp[105][105];

int dfs(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= n){
        return INT_MAX;
    }
    if(x == 0 && y== 0){
        return a[0][0];
    }
    if(dp[x][y] != -1){
        return dp[x][y];
    }
    dp[x][y] = a[x][y] + min(dfs(x-1, y), min(dfs(x, y-1), min(dfs(x+1, y), dfs(x, y+1))));
    return dp[x][y];
}


int main(){
    int tt;
    cin >> tt;
    while(tt--){
        int n;
        cin >> n;
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> a[i][j];
                dp[i][j] = -1;
            }
        }
        cout << dfs(n-1, n-1) << endl;
    }
    return 0;
}



Example:
Input:
2
5
31 100 65 12 18 10 13 47 157 6 100 113 174 11 33 88 124 41 20 140 99 32 111 41 20
2
42 93 7 14

Output:
327
63

在两种情况下我都得到2147483647作为输出，这是INT_MAX的值。

Answer 1

n所查看的全局变量dfs始终为零（通过静态初始化），它从未分配值。当main调用，例如dfs(4, 4)时，由于INT_MAX检查，该函数立即返回4 >= 0。

---

一旦解决了这个简单的问题，就会发现程序由于堆栈溢出而崩溃。您会看到，dfs(4, 4)调用dfs(3, 4)，依次调用dfs(4, 4)，后者调用dfs(3, 4)，然后...

这实际上不是动态编程问题。这是一个“图形中的最短路径”问题，适用于Dijkstra或A *算法。