計蒜客 跳躍遊戲二

題目

描述

給定一個非負整數數組，假定你的初始位置為數組第一個下标。

數組中的每個元素代表你在那個位置能夠跳躍的最大長度。

你的目标是到達最後一個下标，并且使用最少的跳躍次數。

例如：

A = [2,3,1,1,4]A=[2,3,1,1,4]，到達最後一個下标的最少跳躍次數為 22。（先跳躍 11 步，從下标 00 到 11，然後跳躍 33 步，到達最後一個下标。一共兩次）

輸入格式

第一行輸入一個正整數 n(1 \le n \le 100)n(1≤n≤100) ，接下來的一行，輸入 nn 個整數，表示數組 AA。

輸出格式

最後輸出最少的跳躍次數。

樣例輸入

5
3 1 1 1 1
           

樣例輸出

2
           

題解

DP

若目前位置 i 可以由前面的某個點j跳過，那麼就在目前點 i 的最小步數就是min( f [j]+1, f [i])

代碼

#include<cstdio>
#include<cstring>
using namespace std;

int n;
int a[],f[];

int readln()
{
    int x=;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while ('0'<=ch&&ch<='9') x=x*+ch-,ch=getchar();
    return x;
}

int min(int x,int y){return x<y?x:y;}

int main()
{
    memset(f,,sizeof(f));
    n=readln();f[]=;
    for (int i=;i<=n;i++) a[i]=readln();
    for (int i=;i<=n;i++)
        for (int j=;j<i;j++)
            if (j+a[j]>=i) f[i]=min(f[i],f[j]+);
    printf("%d",f[n]);
    return ;
}