Dynamic Programming - Counting Ways to Reach Nth Stairs

Introduction

• Problem Statement: Count the number of distinct ways to reach the nth stair from the 0th stair.
• Constraints: You can climb either one step or two steps at a time.

Problem Example

• Given n = 3:
  • 1 → 1 → 1 → 3
  • 0 → 2 → 1 → 3
  • 0 → 1 → 2 → 3
• Output: 3 distinct ways

Identifying a Dynamic Programming (DP) Problem

1. Count Total Number of Ways: When asked to count total ways, it's often a recursive problem.
2. Multiple Possible Ways: Problems asking for minimum or maximum outcomes among multiple ways are good candidates for recursion and DP.
3. Recursion as a Base: Try all possible ways using recursion, then think about converting it to DP.

Steps to Approach the Problem

1. Representation in Terms of Index: Represent the problem as an index-based problem.
2. Perform All Possible Actions on Index:

• Jump one stair
• Jump two stairs

3. Sum Up Results:

• If counting ways: Sum up the distinct ways from all actions.
• If looking for minimum/maximum: Take the min/max of the actions.

Example of Translating to Recurrence

• Base Cases:
  • f(0) = 1
  • f(1) = 1
• Recurrence: f(n) = f(n-1) + f(n-2)
• Insight: Equivalent to the Fibonacci sequence.

Steps to Solve DP Problems

1. Identify Problem Type: Recognize if it's recursive.
2. Write Recurrence Relation:

• Identify the base case(s)
• Identify the transition (i.e., how current state is derived from previous states)

3. Memoization and Tabulation:

• Memoize the results, then tabulate.
• Example for Fibonacci: fib(n) = fib(n-1) + fib(n-2)

Special Considerations

• Large Values (e.g., n = 10^18):
  • Classic DP solutions (O(n) complexity) are inadequate.
  • Utilize Matrix Exponentiation to solve in O(log n) time.

Recap and Key Points

1. Use Index-Based Representation: Convert problem representation into indices.
2. Try All Possible Actions: Perform all feasible actions on current index.
3. Sum/Min/Max of Results: Based on the problem requirement (count, find min/max ways).
4. Recurrence Relation: Deduce recurrence relation; memoize and tabulate.
5. Space Optimization: Optimize space usage after implementing DP.

Conclusion

• Learn and apply the three main points to solve any DP problem:
  1. Represent problem in terms of indices.
  2. Perform all possible actions on indices as per problem constraints.
  3. Sum/min/max results based on problem requirement.
• Focus is on understanding how to build a recurrence first—memoization, tabulation, and optimization follow naturally.