dfs dp boj1546

爬楼梯练习Submit: 83   Accepted:23Time Limit: 1000MS  Memory Limit: 65536KDescription
ZaakDov上高中时经常中午跑出去打魔兽，下午上课总是踩铃。由于每次上课总是匆匆忙忙跑进教室的，所以他需要训练一番不凡的爬楼梯技术。
又是一次快速爬楼梯练习，不过这次竟然出现了楼梯上有水果皮的场景，这让ZaakDov不得不选择以那些楼梯为落脚点（否则踩上去回摔跟头的哟，在楼梯上 摔跟头时可是件很惨的事情）。喜爱数学的他早已知道没有水果皮时应有多少种爬楼梯方法，但是这次有了水果皮就得自己推算了。
现在想推测一下一共有多少种爬楼梯方法。
假设他一次能迈出1到p步阶梯，共有n步阶梯，保证楼梯最后一步阶梯没有水果皮。
你能判断出有多少种爬法吗？


Input
多组测试数据。
每组第一行三个整数n,m,p(1<=n<=1000,1<=m<=n-1,1<=p<=n)，接下来m行每行一个整数x，表示第x阶楼梯上有水果皮，同一组测试数据中不会出现两个或两个以上相同的x。
输入以3个-1结束。



Output
对每组测试数据输出其结果（共有多少种爬楼梯方法）。
最后3个-1不用处理。


Sample Input

3 1 3
2
3 0 2
3 1 2
2
4 0 3
-1 -1 -1


Sample Output

2
3
1
7

两个解法：
dfs超时。
换dp过的

/*
 * dfs TLE, try dp again, see 1546b.c
 * */

#include 
#include 

int fruit[1010], count;
int n, m, p;

void dfs(int current)
{
    if (current > n)
        return;
    if (fruit[current] == 1)
        return;
    count++;
    int i;
    for (i=1 ; i

    {
        dfs(current + i);
    }
}

int main(int argc, char *argv[])
{
    int i, t;
    while (scanf("%d %d %d", &n, &m, &p))
    {
        if (-1 == n && -1 == m && -1 == p)
            break;
        memset(fruit, 0, sizeof(fruit));
        count = 0;
        for (i=0 ; i        {
            scanf("%d", &t);
            fruit[t] = 1;
        }
        dfs(1);
        printf("%d\n", count);
    }
}

/* 很简单的dp,注意输出是long long，初始化条件method[0]=1 */
#include 
#include 

int fruit[1010];
long long method[1010];

long long dp(int n, int p)
{
    int i, j;
    for (i=1 ; i<=n ; i++)
    {
        for (j=i-p ; j        {
            if (j < 0 || 1 == fruit[j] || 1 == fruit[i])
                continue;
            method[i] += method[j];
        }
    }
    return method[n];
}

int main(int argc, char *argv[])
{
    int n, m, p, i, t;
    while (scanf("%d %d %d", &n, &m, &p))
    {
        if (-1 == n && -1 == m && -1 == p)
            break;
        memset(fruit, 0, sizeof(fruit));
        memset(method, 0, sizeof(method));
        method[0] = 1;
        for (i=0 ; i        {
            scanf("%d", &t);
            fruit[t] = 1;
        }
        printf("%lld\n", dp(n, p));
    }
}