Number of ways to reach Nth floor by taking at-most K leaps

Given N number of stairs. Also given the number of steps that one can cover at most in one leap (K). The task is to find the number of possible ways one (only consider combinations) can climb to the top of the building in K leaps or less from the ground floor.

Examples:

Input: N = 5, K = 3
Output: 5
To reach stair no-5 we can choose following combination of leaps:
1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
2 3
Therefore the answer is 5.

Input: N = 29, K = 5
Output: 603

思路：先尝试1步的种类数，然后再尝试多步，直到k步，注意选择条件的循环因该放在外层。

#include
   
    using namespace std;int get(int n, int k){    int dp[n+1];    memset(dp,0,sizeof(dp));    dp[0] = 1;    for(int i = 1; i <= k; ++i){        for(int j = 0; j <= n; ++j){            if(j-i >= 0 )                dp[j] += dp[j-i];        }    }// 错误 循环 选择循环 应放在外面//    for(int i = 1; i <= n; ++i){//        for(int j = 1; j <= k; ++j){//            if(i-j >= 0)//                dp[i] += dp[i-j];//        }//    }    return dp[n];}int main()    {        int n,k;        int t;        scanf("%d%d",&n,&k);        printf("%d\n",get(n,k));        return 0;    }

转载地址：http://nwsmi.baihongyu.com/

你可能感兴趣的文章