宝贝，生日快乐！！！LevOJ P1809 wzy的跑步

思路：

wzy每次可以跳 1 到 k 个单位长度的正整数，那么对于任意一个位置 i ，可能由 [i-k,i-1] 中的任意一个位置跳跃而来，即有 k 种状态。若要在 i 的位置踩到的水坑数最少，那么在到达 i 之前的那个位置所踩的水坑数也要最少。是否需要将踩到的水坑数 +1 ，则只需要判断位置 i 是否在水坑内。

设 dp[i] 为位置 i 所踩的水坑数，water[i] 表示位置 i 是否是水坑， j 表示跳了多远，则有状态转移方程：

$dp[i]=min(dp[i],dp[i-j]+water[i])$

AC代码：

#include<bits/stdc++.h>

using namespace std;

int dp[100005];
int water[100005];

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int pos;
    for(int i=1;i<=n;i++){
        dp[i]=99999;
    }
    for(int i=1;i<=m;i++){
        cin>>pos;
        water[pos]=1;
    }
    dp[1]=water[1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(i-j>=1){
                dp[i]=min(dp[i],dp[i-j]+water[i]);    
            }
        }
    }
    cout<<dp[n];
    return 0;
}