program to find the number of ways we can climb n number of steps, given that we can take k maximum steps at a time. Also we cannot take a 0 number step.Solution using dynamic programming.

Steps.cpp

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<time.h>

using namespace std ;

int pow(int n, int k){
	int return_value = 1 ;
	if(k == 0) return 1 ;
	
	for(int i = 0 ; i < k ; i++){
		return_value *= n ; 
	}
	
	return return_value ;
}

int main() {
	unsigned long int number ;
  cout << "Enter the number of steps to climb" << endl ;
  cin >> number ;
        
  unsigned long int k ;
  cout << "Enter the maximum number of steps possible at a time" << endl ;
  cin >> k ;
        
  clock_t t_start = clock() ;
        
  unsigned long int *s = new unsigned long int[number+1] ;
        
  for(long int i = 1 ; i <= k ; i++){
  	s[i] = pow(2,i-1) ;
  }
        
  for(long int i = k+1 ; i <= number ; ++i){
  	for(long int j = i-1 ; j >= i-k ; j--){
    	s[i] += s[j] ;
    }
  }
        
        
  cout << "The number of ways are " << s[number] << endl ;
        
  cout << double(clock() - t_start) / (double)CLOCKS_PER_SEC << " seconds." << endl ;
        
  return 0 ;
}