$Description$

大家都說要勞逸結合，$Ayumi,Mitsuhiko,Genta$畫完方格就出去運動啦！
他們來到了一片空地，畫了N個連續的方格，每個方格上隨機填上了一個數字，大家從第一個格子開始，每次可以向后跳不超過當前格子上的數的步數，大家開始就此比賽，看誰跳到最后一個格子的步數最少。
作為隊長的$Genta$顯然是想獲得勝利的，所以他打電話給$Conan$求助，可是$Conan$在玩游戲，所以就向你求助了。

$Input$

輸入第一行包含一個整數$N$，表示畫的格子的個數。
第二行包含N整數，表示每個格子上的數$ai$。

$Output$

輸出一行，表示跳的最少步數。

$SampleInput$

5 2 3 1 1 1

$SampleOutput$

2

$Explain$

對于40%的數據滿足N<=10，ai<=10。
對于100%的數據滿足N<=5000，ai<=1000。

$Train$ $Of$ $Thought$

設$f[j]$為到$j$這個格子所要的最小步數
動態轉移方程為：
$f[j]=min(f[i]+1,f[j])$

$Code$

#include<cstdio> #include<iostream> #include<cstring> #include<cstdio> using namespace std; int f[5005],a[5005],n; int main() {memset(f,0x7f,sizeof(f));scanf("%d",&n);for (int i=1; i<=n; ++i)scanf("%d",&a[i]);f[1]=0;for (int i=1; i<=n; ++i)//枚舉起跳格子for (int j=i+1; j<=i+a[i]; ++j)//枚舉跳的到的格子f[j]=min(f[i]+1,f[j]);printf("%d",f[n]); }

總結

以上是生活随笔為你收集整理的【DP】跳格子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。