时间戳

首页 > 解决方案 > 具有回溯和 DP 的不同输出

c++ - 具有回溯和 DP 的不同输出

问题描述

我正在使用 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("%lld\n",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。

标签： c++c++14

解决方案

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。使用您的方法，您将计算（无需）所有可能的路线。

推荐阅读