Climbing Stairs Variable Jumps

Fastrail08

May 19th, 2025

497

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.10 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
/*
QUESTION - Count all the ways to reach nth stair from 0th stair
*/
int variableJumpStairs(int stair, int &n, vector<int> &jumps, int &count, vector<int> &memo){
//invalid case
if(stair > n){
return 0;
}
// base case
if(stair == n){
count++;
return 1;
}
//memo check
if(memo[stair] != 0){
return memo[stair];
}
//level - each stair
// options - jumps available from each stair
int allPathsFromCurrStair = 0;
for(int i = 1; i <= jumps[stair]; i++){
allPathsFromCurrStair += variableJumpStairs(stair + i, n, jumps, count, memo);
}
return memo[stair] = allPathsFromCurrStair;
}
int variableJumpStairsDP(int &n, vector<int> &jumps){
//1. Storage & Meaning - dp[i] = how many ways to reach nth stair from ith stair
vector<int> dp(n + 1, 0);
//2. Direction - We need to reach nth from 0th,smaller problem will be when we are standing at nth stair,
//count the number of ways to reach nth stair when you are standing at nth stair = 1
// largest problem = dp[0] ; smallest problem = dp[n + 1]
dp[n] = 1;
//3. Travel & Solve - Travel in the direction of small problem to large problem & return the original largest problem
//Here at dp[0] and not at dp[n + 1].
for(int i = n - 1; i >= 0; i--){
for(int j = 1; j <= jumps[i]; j++){
if(i + j <= n + 1){
dp[i] += dp[i + j];
}
}
}
return dp[0];
}
int main() {
// your code goes here
int n;
cin >> n;
vector<int> jumps(n);
for(int i = 0; i < n; i++){
cin >> jumps[i];
}
int count = 0;
vector<int> memo(n + 1, 0);
//memo call(return method)
cout << variableJumpStairs(0, n, jumps, count, memo) << '\n';
//memo call (print method) it will not work now, as we are not reaching base case everytime because of memo check
// cout << count << '\n';
//dp call
cout << variableJumpStairsDP(n, jumps) << '\n';
}

Add Comment

Please, Sign In to add comment