Time Complexity for Unique Paths Using Memoization

1. Recursive Calls:
   • The function findPaths is called recursively to compute the number of unique paths to each cell in the m x n grid.
   • Number of Unique States: Each state is defined by a unique (row, col) combination, and there are O(m \cdot n) such unique states in the grid.
   • Number of Recursive Calls:
     • Each unique state is computed only once, as we use memoization. This prevents redundant recursive calls and ensures each state is solved once.
   • Overall Time Complexity: O(m \cdot n)

Space Complexity for Unique Paths Using Memoization

1. Memoization Map (memo):

   • The memo map stores results for each unique state (row, col), so it has space complexity O(m \cdot n).
   • The size of the String keys is insignificant compared to the number of entries, so this does not impact the space complexity significantly.

2. Recursive Call Stack:

   • Maximum Depth:
     • The maximum depth of the recursive call stack is O(m + n) in the worst case, representing the diagonal traversal of the grid from (m-1, n-1) to (0, 0).

3. Overall Space Complexity:

   • The total space complexity accounts for both the memoization map and the call stack depth: O(m \cdot n), for storing results, plus O(m + n) for the recursion stack.

2. Solving a Problem with Top-Down DP

Problem: Calculate the minimum cost to climb a staircase where each step has a certain cost associated with it. You can climb one or two steps at a time.

Time Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

1. Recursive Calls:
   • The function findMinCost is called recursively to compute the minimum cost for each step i.
   • Number of Unique Subproblems:
     • Each index from 0 to n-1 (where n is the length of the cost array) represents a unique subproblem.
     • Since each subproblem is computed only once due to memoization, the total number of recursive calls is O(n).
2. Key Operations:
   • Base Case Checks:
     • The checks if (i < 0), if (i == 0 || i == 1), and if (dp[i] != -1) run in O(1).
   • Recursive Calculations:
     • For each call to findMinCost, two recursive calls are made (findMinCost(cost, i - 1) and findMinCost(cost, i - 2)), but due to memoization, each index is only processed once.
   • Filling and Returning Values:
     • Storing and returning values in dp[i] take O(1).

Overall Time Complexity:

• Each index i from 0 to n-1 is processed once, leading to a total time complexity of: O(n)

Space Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

1. DP Array (dp):

   • The dp array is used to store precomputed results for each index from 0 to n-1, taking O(n) space.

2. Recursive Call Stack:

   • Maximum Depth of Recursion:
     • The maximum depth of the recursion is O(n), which occurs when the function is called starting from the highest index down to 0.
   • Space Complexity for Call Stack: O(n)

   The space used by the recursion stack can go up to O(n) in the worst case.

3. Solving a Problem with Bottom-Up DP

Problem: Find the length of the longest palindromic subsequence in a given string.