Introduction to Dynamic Programming

Welcome to our next exciting lesson, where we introduce the basics of Dynamic Programming (DP) — a powerful method for solving optimization, combinatorics, and other complex problems. Dynamic Programming solves problems by breaking them into smaller subproblems and reusing previously computed results instead of solving the same subproblems multiple times.

Not every problem can be solved with DP. To identify if a problem is a candidate for this approach, look for two key properties:

1. Optimal Substructure: The optimal solution to the problem can be constructed from the optimal solutions of its subproblems.
2. Overlapping Subproblems: The algorithm solves the same subproblems repeatedly rather than generating new ones.

There are two primary ways to implement a DP solution:

1. Top-Down (Memoization): You start with the main problem and recursively break it down. When a subproblem is solved, you store the result in a "memo" (like a MutableMap or an array) to reuse later.
2. Bottom-Up (Tabulation): You start by solving the smallest subproblems first and use their results to build up to the main problem. This is usually implemented iteratively using an array (IntArray or LongArray), which is often more memory-efficient than a map.

As you may recall, computing the $N$-th Fibonacci number using simple recursion leads to exponential time complexity $O(2^N)$. Here is the Top-Down approach using memoization, which reduces this to linear time:

// Time Complexity: O(N)
// Space Complexity: O(N) due to recursion stack and memo map
fun fibonacciMemo(n: Int, memo: MutableMap<Int, Long>): Long {
    if (memo.containsKey(n)) return memo[n]!!
    if (n <= 1) return n.toLong()

    val result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo)
    memo[n] = result
    return result
}

Alternatively, we can use the Bottom-Up approach. We use a LongArray to store results. This "tabulation" method fills the table from index 0 up to n:

// Time Complexity: O(N)
// Space Complexity: O(N) for the DP array
fun fibonacciTab(n: Int): Long {
    if (n <= 1) return n.toLong()
    
    // Create an array to store calculated values
    val dp = LongArray(n + 1)
    
    // Initialize base cases
    dp[0] = 0
    dp[1] = 1
    
    // Build the solution iteratively
    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    
    return dp[n]
}

By using an array, we benefit from faster access times and lower overhead compared to a map. In many interview scenarios, the bottom-up approach is preferred because it avoids the overhead of recursion depth (stack overflow).