c++ - 动态规划问题 - 最小成本路径

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* 算法。