哪个大佬能用记忆化搜索优化一下dfs啊
查看原帖
哪个大佬能用记忆化搜索优化一下dfs啊
1202745
jinbaobei1212楼主2025/7/1 10:01
#include<bits/stdc++.h>
using namespace std;
int n,a,b,k[250],vis[250],ans=INT_MAX;
void dfs(int t,int dp){
    if(dp>=ans)return;
    if(t<=0)return;
    if(t>n)return;
    if(vis[t])return;
    if(t==b){
        ans=min(ans,dp);
        return;
    }
    vis[t]=1;
    dfs(t+k[t],dp+1);
    dfs(t-k[t],dp+1);
}
int main(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)cin>>k[i];
    dfs(a,0);
    if(ans!=INT_MAX)cout<<ans;
    else cout<<-1;
    return 0;
}
2025/7/1 10:01
加载中...