Climbing Stairs

#include <bits/stdc++.h>
using namespace std;

//Question - Count the number of paths from nth Stair to 0th Stair


// Another way of thinking is to break it down into levels and options
// Levels - Each Stair
// Options - 3 possible jumps from each stair

// Recursive code + memo
int countStairPath(int n, vector<int> &memo){
    // base case
    if(n == 0){
        return 1;
    }

    //invalid case
    if(n < 0){
        return 0;
    }

    //memo check
    if(memo[n] != 0){
        return memo[n];
    }
    //paths from n - 1
    int pathsNm1 = countStairPath(n - 1, memo);
    //path from n - 2
    int pathsNm2 = countStairPath(n - 2, memo);
    //path from n - 3
    int pathsNm3 = countStairPath(n - 3, memo);


    return memo[n] = pathsNm1 + pathsNm2 + pathsNm3;
}


//dp code
int getStairPath(int n){
    // dp array (as we need the answer for n, so N + 1 size required)
    vector<int> dp(n + 1);

    /*
    1) MEANING
    dp[n] = total number of paths from n to 0th stair
    generally each cell will answer the same question but with smaller param
    Each cell holds the answer to all the possible unique recursive states

    2) DIRECTION
    smaller problem is at dp[0]
    dp[0] - stores answer for all the paths from 0th stair to 0th stair = 1
    so direction to solve would be from smaller problem to larger problem 0 -> n

    3) TRAVEL & SOLVE
    loop in the direction
    */

    // ASSIGN VALUE TO BASE CASE as we did in memo code
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        if(i == 1){
            dp[i] = dp[i - 1];
        }
        else if(i == 2){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        // to figure out to which dp[i] is related just see the recursion tree, and watch which state is calling which states to get the answer.
        else{
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }
    }
    return dp[n];
}

int main() {
    // your code goes here
    int n;
    cin >> n;
    vector<int> memo(n + 1, 0);
    //cout << countStairPath(n, memo) << '\n';
    cout << getStairPath(n) << '\n';
}