过桥(牛客)（逆推dp）

过桥(牛客)（逆推dp）

原题链接：登录—专业IT笔试面试备考平台_牛客网

 思路：

其实如果走到一个a[i]是负数的地方，也就是要倒退，这样是没有用的。因为如果说前面还有a[i]大于0，我倒退回去了然后下一步能走到更远的地方，但是这样用的步数比之前就在那个地方的步数要多啊。所以说如果a[i]< 0，对答案是没有贡献的。

我把没有贡献地方dp的时候设置为-1，那么下次碰到就直接跳过。n不大，双重循环能过。 

看了大佬思路我自己写的代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))int a[2010];
int f[2010];int main(){int n; scanf("%d", &n);rep(i, n) scanf("%d", &a[i]);memset(f, 0x3f, sizeof f);for(int i = n - 1;  i >= 1; i--){if(a[i] < 0) f[i] = -1;else{if(i + a[i] >= n) f[i] = 1;else{for(int j = i + 1; j <= i + a[i]; j++) if(f[j] > 0) f[i] = min(f[j] + 1, f[i]);}}}if(f[1] == -1 || f[1] == INF) printf("-1");else printf("%d", f[1]);return 0;
}

 参考大佬：【牛客oj】过桥（逆推dp）__C9的博客-CSDN博客

大佬写的很详细，有时候忘记了可以去看看~

大佬代码(dp[n]设为0，碰到a[i]为负数直接略过）

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[2010];
int dp[2010];   //从1到i所需要的最小花费
int main()
{memset(dp,INF,sizeof(dp));scanf("%d",&n);dp[n]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=n-1;i>=1;i--){if(a[i]<0)    continue;    //产生回跳无意义else if(a[i]>0)    //枚举可到达的每个节点，寻找最小值{for(int j=i+1;j<=i+a[i];j++){dp[i]=min(dp[i],dp[j]+1);}}}if(dp[1]==INF)  printf("-1n");else printf("%dn",dp[1]);//system("pause");return 0;
}