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.

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

Understanding DP is about recognizing how to break a large problem into smaller, interrelated tasks. In the following exercises, you will practice identifying these subproblems and implementing both memoization and tabulation techniques. Get ready to jump in!