you are at the bottom of a staircase with n stairs. you can jump 1, 2, or 3 stairs at a time. how many different ways can you jump up the stairs? in csharp

Here's a C# code to solve the problem using dynamic programming (memoization):

main.cs
public static int CountWaysToJumpStairs(int n)
{
    int[] memo = new int[n + 1]; // memoization array
    memo[0] = 1; // one way to jump zero stairs
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; (j <= 3) && (i - j >= 0); j++)
        {
            memo[i] += memo[i - j]; // build the answer using the previous subproblems
        }
    }
    
    return memo[n];
}
390 chars
16 lines

The idea is to use memoization to store subproblems that can be repeated in the future to compute the answer efficiently. We initialize the memo array with a size n + 1, where memo[i] represents the number of ways to jump i stairs. We start with memo[0] = 1, because there is only one way to jump zero stairs (do nothing).

Then, we use a double loop to iterate over all stairs and possible jumps from 1 to 3. We build the answer incrementally by using the previously computed subproblems, stored in memo, so we don't have to repeat them. Finally, we return memo[n], which holds the answer to the problem.

This algorithm has a time complexity of O(n) and a space complexity of O(n), because we need to store the solutions to all subproblems. The recursive version has a higher time complexity (O(3^n)), because it repeats subproblems unnecessarily.