动态规划问题-Minimum成本路径

Question

我试过这个问题-- Minimum Cost Path。我已经用Dijkstra的最短路径算法解决了这个问题。但是，当我尝试使用recursion+memoisation，即使用动态编程时，我卡住了，无法调试我的代码。我需要帮助，看看我的代码哪里错了！

我真的很高兴能得到你的帮助。

#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

dfs查看的全局变量n总是零(通过静态初始化)，它从未被赋值。当main调用dfs(4, 4)时，由于4 >= 0检查，该函数立即返回INT_MAX。

一旦你修复了这个简单的问题，你会发现你的程序由于堆栈溢出而崩溃。您看，dfs(4, 4)调用dfs(3, 4)，而dfs(4, 4)又调用dfs(3, 4)，后者...

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