关于C++动态规划，请问代码bug在哪儿？

Question

这道问题起源洛谷

我用动态规划来写，solve(i,j)表示第 i 次调音调到 j 可不可行，true代表可行，false代表不可行
那么i>1时，solve(i,j)=true当且仅当 0<=j - a[j]<=maxlevel && solve(i - 1, j - a[j]) == true
或 0<=j +a[j]<=maxlevel && solve(i - 1, j +a[j]) == true
以下是我用这个思路写的代码

#include<iostream>
using namespace std;

int n, bl, ml;
int a[51];

bool in(int n) {
    if (n >= 0 && n <= ml) {
        return true;
    }
    else {
        return false;
    }
}
bool solve(int i, int j) {
        if (i == 0) {
            if (j == bl) {                
                return true;
            }
            else {                
                return false;
            }
        }
        else{
            if (in(j - a[j]) == true && (solve(i - 1, j - a[j]) == true)) {                
                return true;
            }
            else if (in(j + a[j]) == true && (solve(i - 1, j + a[j]) == true)) {                
                return true;
            }
            else {                
                return false;
            }
        }
    
}

int main() {
    cin >> n >> bl >> ml;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }    
    for (int j = ml;j >= -1;j--) {
        bool ans2 = solve(n, j);
        if (ans2 == true) {
            cout << j;
            break;
        }
        if (j == -1) {
            cout << -1;
        }        
    }
}

但是程序好像有bug，输入样例不对

请问bug在哪儿？

Answer 1

动态规划的背包问题。

但是如果把这道题强行理解为01背包未免有些和01背包的概念不符，其实这道题是到达性的01背包。

我们可以不把这道题想象的那么复杂，直接按照最基础的动态规划来，设置动态转移方程和初值。

这回我们用标记数组来动归。

设状态转移方程f[i][j]为第i首歌能否达到j的音量，能为1，不能为0。

这样的话我们就可以开始动归，最后只需要枚举出最大的f[n][i]，就是需要找的答案了。

这里还需要注意，初值f[0][begin]要设置为1，因为没开始之前就可以达到begin的音量。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,beginlevel,maxlevel;
int c[60];
int f[60][1010];
int main()
{
    scanf("%d%d%d",&n,&beginlevel,&maxlevel);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    f[0][beginlevel]=1;
    for(int i=1;i<=n;i++)
        for(int j=maxlevel;j>=0;j--)
        {
            if(f[i-1][j] && j+c[i]<=maxlevel)
                f[i][j+c[i]]=1;
            if(f[i-1][j] && j-c[i]>=0)
                f[i][j-c[i]]=1;
        }
    for(int i=maxlevel;i>=0;i--)
        if(f[n][i]==1)
        {
            printf("%d",i);
            return 0;
        }
    printf("-1");
    return 0;
}

DFS也行

#include<bits/stdc++.h>
#define ll long long
#define reg register
using namespace std;
int bl,ml,ans,c[55],n;
bool f[51][1010];//定义t是否能达到k的音量
void dfs(int t,int k){
    if(k<0||k>ml)return;
    //剪枝部分↓
    if(f[t][k])return;
    //如果改点已经有了
    //就不要再搜了
    else f[t][k]=1;//否则算他访问过了
    //剪枝部分↑
    if(t==n){
        ans=max(ans,k);
        return;
    }
    dfs(t+1,k+c[t+1]);
    dfs(t+1,k-c[t+1]);
}
int main(){
    ans=-1;
    scanf("%d%d%d",&n,&bl,&ml);
    for(reg int i=1;i<=n;++i){
        scanf("%d",&c[i]);
    }
    dfs(0,bl);
    cout<<ans;
    return 0; 
}