Table of Content

Nth Fibonacci Number

• Problem: Find the Nth Fibonacci number, which follows a sequence where each number is the sum of the two preceding ones.
• Recursive Approach: Uses a call stack tree, but involves repeated calculations for the same subproblems.
• Memoization:
  • Implement by creating an array DP of size N, initially filled with 1.
  • Pass DP into the recursive function.
  • Save intermediate results in DP to avoid recalculating subproblems.
  • Time complexity: O(N), Space complexity: O(N) (array + call stack).
• Tabulation:
  • Bottom-up approach, using an iterative method.
  • Initialize base cases directly in the array.
  • Use a loop to fill the array from the simplest subproblem to the most complex.
  • Time and space complexity: O(N).

Maximum Sum of Non-Adjacent Elements

• Problem: Find the highest possible sum of non-adjacent elements in an array.
• Recursive Approach:
  • Use a "pick or not pick" strategy.
  • Base cases: index out of bounds or at the start.
  • Time complexity: O(2N), Space complexity: O(N) (call stack).
• Memoization:
  • Create an array DP of size N, initially filled with 1.
  • Use the DP array to store results of subproblems.
  • Time complexity: O(N), Space complexity: O(N) (array + call stack).
• Tabulation:
  • Use a bottom-up approach to fill the DP array iteratively.
  • Initialize base cases in the array and fill subsequent values using a loop.
  • Time and space complexity: O(N).

Ninja's Training Schedule (2D DP Problem)

• Problem: Maximize merit points over N days with constraints on consecutive activities.
• Recursive Approach:
  • Consider all activities for each day and track the last activity done.
  • Use two indices: day and last (last activity index).
  • Time complexity: O(2^N), Space complexity: O(N) (call stack).
• Memoization:
  • Create a 2D array dp of size N×4 to store results.
  • Use the dp array to store results of subproblems based on day and last.
  • Time complexity: O(N×4), Space complexity: O(N×4).
• Tabulation:
  • Initialize a 2D array dp to store maximum merit points for each day and each possible last activity.
  • Use nested loops to fill the array from the base cases upwards.
  • Time and space complexity: O(N×4).

Grid Unique Paths

• Problem: Find all unique paths from the start to the end of an MxN grid, only moving right and down.
• Recursive Approach:
  • Express problem in terms of grid indices.
  • Base cases: out of bounds or reaching the destination.
  • Time complexity: O(2^M+N), Space complexity: O(M+N) (call stack).