具有回溯和DP的不同输出

Question

我正在使用DP来解决问题，但是没有DP的解决方案，即只是回溯给出了正确的输出，而DP的相同代码给出了错误的输出。想不通为什么。

链接到问题 - https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1278

这是代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define oo 1000000007;
lli dp[12][1005];
int a[10][1005];
int n;
lli calc(int alt,int i){
if(dp[alt][i] != -1) {
return dp[alt][i];
}
if(i==n && alt==0) {
return 0;
}
if(alt>9 || alt<0 || i==n) {
return oo;
}
return dp[alt][i] = min(
min(
lli(30) - a[alt][i] + calc(alt  ,i+1),
lli(20) - a[alt][i] + calc(alt-1,i+1)
),
lli(60) - a[alt][i] + calc(alt+1,i+1)
);
}
int main(){
int t;
string bl;
scanf("%d",&t);
while(t--){
getline(cin,bl);
memset(dp,-1,sizeof dp);
scanf("%d",&n);
n = n/100;
for(int i=9; i>=0; i--) {
for(int j=0; j<n; j++) {
scanf("%d",&a[i][j]);
}
}
lli ans = calc(0,0);
printf("%lldn",ans);
if(t!=0) printf("n");
}
}

输入为

1
400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1

正确的输出是 120。

Answer 1

if(dp[alt][i] != -1) {
return dp[alt][i];
}
lli(20) - a[alt][i] + calc(alt-1,i+1)

你只是(不(幸运，程序没有直接崩溃你！

对于alt == -1，你只读取一些关于递归的随机垃圾。您正在从dp数组外部读取随机值。

像这样切换它们，它应该可以工作(或者至少具有定义的行为(：

if(i==n && alt==0) {
return 0;
}
if(alt>9 || alt<0 || i==n) {
return oo;
}
if(dp[alt][i] != -1) {
return dp[alt][i];
}

---

无论哪种方式，您的方法都行不通。您首先遍历深度(找到任何路径！(，但遍历顺序必须首先宽阔才能找到最短的路线。

这意味着你不能像这样使用递归，而必须通过内部循环alt和外部循环i进行迭代。然后，您可以逐步填写路径字段。

---

像这样的朴素动态编程并不是完成此任务的最佳解决方案。您最好将其视为有向加权图，并应用标准Dijkstra。使用您的方法，您将计算(无需(所有可能的路线。