首页 > 其他 > 详细

题目1389:变态跳台阶 简单DP

时间:2015-08-29 15:23:37      阅读:105      评论:0      收藏:0      [点我收藏+]

http://ac.jobdu.com/problem.php?pid=1389


这样的题只要分类不要重复就没问题了。

可以分为,

第一次跳0步,也就是直接跳到终点。

第一次跳1步,然后在跳f(i-1)

第一次跳2步,然后在跳f(i-2)

...

DP我果断是弱爆了,第一次写居然把第一次跳的那个+1,想了下A了

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

#define LL long long
const int SIZE = 50+1;
int n;
LL f[SIZE];

void init(){
    f[1]=1;
    f[0]=0;
    for(int i=2;i<=50;i++){
        f[i] = 1;
        for(int j=1;j<i;j++){
            f[i] += f[i-j];
        }

    }
}

int main(){
    init();
    while(cin >> n){
        cout << f[n] << endl;
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

题目1389:变态跳台阶 简单DP

原文:http://blog.csdn.net/u011026968/article/details/48087609

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!