c++ - 动态规划问题 - 最小成本路径
问题描述
我正在尝试这个问题 -最低成本路径。我已经使用 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 的值。
解决方案
查看的全局变量n
始终dfs
为零(通过静态初始化),它从未分配过值。例如,当main
调用 时,由于检查dfs(4, 4)
,该函数立即返回。INT_MAX
4 >= 0
一旦你解决了这个简单的问题,你会发现你的程序由于堆栈溢出而崩溃。你看,dfs(4, 4)
调用dfs(3, 4)
,又调用dfs(4, 4)
,调用dfs(3, 4)
,...
这不是一个真正的动态规划问题。这是一个“图中的最短路径”问题,适用于例如 Dijkstra 或 A* 算法。