动态规划入门
会长大人非常喜欢玩《塞尔达传说:旷野之息》，有一天，手残的会长大人lj拜托游戏达人lmj帮忙开启最困难的第120个祠堂，这个祠堂的通过方法可以转化为一个一维问题。你初始在0这个位置，终点是n这个位置，你每次最多可以跳3格。很不幸的是，有些位置是有陷阱的，每踩一下扣一点血，你开始有k点血，也就是说你最多踩k-1个陷阱。问跳到终点不死有多少种跳法，保证有解。
lmj一看这个问题实在是太简单了，所以把这个任务交给了你。
Input
单组样例
一个整数n，代表有n格(1<=n<=20)
一个整数m，代表有m个陷阱(1<=m<=n)
一个整数k，代表有k点血(1<=k<=m+1)
接下来有m个互不相同的整数，代表这些格子有一个陷阱。(1<=ai<=n)
Output
跳到终点有几种跳法
Sample Input
3 0 1
3 3 1
1 2 3
3 3 1
1 2 3
Sample Output
4
0
0
解题思路：
设dp[i][j]代表走到第i个位置还剩j滴血，如果当前格为陷阱，dp[i][j]=dp[i-1][j+1]+dp[i-2][j+1]+dp[i-3][j+1],
如果当前格不为陷阱，dp[i][j]=dp[i-1][j];+dp[i-2][j]+dp[i-3][j];
最后统计dp[n][1]--dp[n][k]的和即可
ac代码：
using namespace std;
int main()
{
int n,m,k,i,a[25],dp[25][25],a1,j,sum=0;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
scanf("%d%d%d",&n,&m,&k);
dp[0][k]=1;
for(i=1;i<=m;i++){
scanf("%d",&a1);
a[a1]=1;
}
for(i=1;i<=n;i++){
for(j=1;j<=k;j++){
if(a[i]==1){
if(i-1>=0) dp[i][j]+=dp[i-1][j+1];
if(i-2>=0) dp[i][j]+=dp[i-2][j+1];
if(i-3>=0) dp[i][j]+=dp[i-3][j+1];
}
else{
if(i-1>=0) dp[i][j]+=dp[i-1][j];
if(i-2>=0) dp[i][j]+=dp[i-2][j];
if(i-3>=0) dp[i][j]+=dp[i-3][j];
}
}
}
for(i=1;i<=k;i++)
sum+=dp[n][i];
printf("%d",sum);
return 0;
}