Dynamic Programming Algorithms

In this lesson, we will explore three different approaches to solving dynamic programming problems with more complex examples:

• Memoization (Top-down approach)
• Top-down DP with Explicit Recursion
• Bottom-up DP (Tabulation)

1. Solving a Problem with Memoization

Problem: Calculate the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid. You can only move right or down.

import java.util.HashMap;
import java.util.Map;

public class Solution {

  private Map<String, Integer> memo = new HashMap<>();

  public int uniquePaths(int m, int n) {
    return findPaths(m - 1, n - 1);
  }

  private int findPaths(int row, int col) {
    // Base case: Reached the start of the grid
    if (row == 0 || col == 0) return 1;

    // Create a unique key for the current position
    String key = row + "," + col;

    // Return the stored result if it exists
    if (memo.containsKey(key)) {
      return memo.get(key);
    }

    // Recursively calculate the number of paths from the left and above
    int paths = findPaths(row - 1, col) + findPaths(row, col - 1);

    // Store the result in the memo
    memo.put(key, paths);

    return paths;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    int m = 3, n = 7; // Example grid size
    int uniquePaths = solution.uniquePaths(m, n);

    System.out.println(
      "Unique Paths for " + m + "x" + n + " grid: " + uniquePaths
    );
  }
}

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 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:

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 .
   • 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 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: , for storing results, plus 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.

import java.util.Arrays;

public class Solution {
    private int[] dp;

    public int minCostClimbingStairs(int[] cost) {
        dp = new int[cost.length];
        Arrays.fill(dp, -1);
        return Math.min(findMinCost(cost, cost.length - 1), findMinCost(cost, cost.length - 2));
    }

    private int findMinCost(int[] cost, int i) {
        if (i < 0) return 0; // Base case: No cost when below the first step
        if (i == 0 || i == 1) return cost[i]; // Base cases for the first two steps

        if (dp[i] != -1) return dp[i]; // Return precomputed result

        dp[i] = cost[i] + Math.min(findMinCost(cost, i - 1), findMinCost(cost, i - 2)); // Compute and store

        return dp[i];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] cost = {10, 15, 20}; // Example cost array
        int minCost = solution.minCostClimbingStairs(cost);

        System.out.println("Minimum cost to reach the top: " + minCost);
    }
}

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 .
2. Key Operations:
   • Base Case Checks:
     • The checks if (i < 0), if (i == 0 || i == 1), and if (dp[i] != -1) run in .
   • 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 .

Overall Time Complexity:

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

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 space.

2. Recursive Call Stack:

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

   The space used by the recursion stack can go up to 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.

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n]; // dp[i][j] represents the length of the longest palindromic subsequence in substring s[i...j]

        // Single characters are palindromes of length 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Fill the table for substrings of length 2 and greater
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + dp[i + 1][j - 1]; // Characters match
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // Take the max excluding either end
                }
            }
        }

        return dp[0][n - 1]; // Length of the longest palindromic subsequence
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        String s = "bbbab"; // Example input
        int longestSubseq = solution.longestPalindromeSubseq(s);

        System.out.println("Longest Palindromic Subsequence length: " + longestSubseq);
    }
}

Time Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

1. Initialization:

   • Single Character Initialization:
     • The for loop that sets dp[i][i] = 1 for each i runs times, where n is the length of the input string s.

2. Nested Loops:

   • The outer loop runs times, as it iterates over lengths of substrings starting from 2 up to n.
   • The middle loop runs times for each length, as it starts from the beginning of the string up to n - len.
   • The inner loop computes the value at dp[i][j], where , and runs operations for each combination.

3. Overall Time Complexity:

   • The number of operations for filling the dp table is because each of the cells in the upper triangle of the 2D array is filled once.
   • Total Time Complexity:

Space Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

1. DP Table (dp):

   • The 2D dp table has a size of , where n is the length of the input string s.
   • Space used by dp:

2. Auxiliary Space:

   • The algorithm does not use any additional data structures that grow with the input size.
   • Overall auxiliary space: .

Overall Space Complexity:

• The total space complexity is:

I just read a lesson on **Dynamic Programming Algorithms** (DSA) and want to truly understand it. Explain Dynamic Programming Algorithms from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Dynamic Programming Algorithms** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Dynamic Programming Algorithms** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Dynamic Programming Algorithms** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.