How To Solve 1 2 2

Of course. Here is a comprehensive, SEO-optimized article about solving the "1 2 2" dynamic programming problem, written to be engaging and educational for readers of all backgrounds.

How to Solve the "1 2 2" Problem: A Deep Dive into Dynamic Programming

The "1 2 2" problem is a classic and deceptively simple puzzle that serves as a perfect introduction to the powerful concept of Dynamic Programming (DP). At its core, the problem asks: Given a target sum n and an infinite supply of coins of denominations 1 and 2, how many distinct ways can you make the sum n? Here's one way to look at it: to make the sum 4, the combinations are: 2+2, 2+1+1, 1+2+1, 1+1+2, and 1+1+1+1, resulting in 5 distinct ways Practical, not theoretical..

While it sounds straightforward, a naive recursive approach quickly becomes inefficient as n grows large. This article will guide you from the basic, flawed solution to the elegant and optimal Dynamic Programming approach, explaining the underlying logic every step of the way.

Understanding the Problem and the Naive Approach

Let's first clarify what we're solving. We are counting the number of ordered sequences of 1s and 2s that add up to n. The order matters, which is why 2+1+1, 1+2+1, and 1+1+2 are considered different solutions.

A natural first instinct is to use recursion. We can break the problem down:

• To form the sum n, the last coin we use can either be a 1 or a 2.
• If the last coin is a 1, then the remaining sum we need to form is n-1. The number of ways to do this is the solution for n-1.
• If the last coin is a 2, then the remaining sum is n-2. The number of ways to do this is the solution for n-2.

This leads to the following recursive formula: ways(n) = ways(n-1) + ways(n-2)

This formula should look familiar—it is the same recurrence relation that defines the Fibonacci sequence. The base cases are:

• ways(0) = 1 (There is one way to make sum 0: use no coins)
• ways(1) = 1 (Only one way: a single 1-coin)

Let's test this for n=4: ways(4) = ways(3) + ways(2) ways(3) = ways(2) + ways(1) ways(2) = ways(1) + ways(0) = 1 + 1 = 2 So, ways(3) = 2 + 1 = 3 And ways(4) = 3 + 2 = 5. This matches our manual count That alone is useful..

The Flaw: Overlapping Subproblems While the recursive formula is correct, implementing it directly leads to exponential time complexity. To calculate ways(4), we need ways(3) and ways(2). To get ways(3), we need ways(2) and ways(1). Notice that ways(2) is calculated twice. For larger values of n, the number of redundant calculations explodes, making the recursive solution extremely slow. This is the classic "overlapping subproblems" property that Dynamic Programming is designed to solve No workaround needed..

The Dynamic Programming Solution: Memoization and Tabulation

Dynamic Programming is a technique for solving complex problems by breaking them down into simpler subproblems. It stores the solutions to these subproblems so that they are not recomputed, drastically improving efficiency. There are two main approaches: top-down (Memoization) and bottom-up (Tabulation).

Approach 1: Top-Down with Memoization

This approach is a direct enhancement of the recursive method. We add a data structure (like an array or a dictionary) to memoize or cache the results of function calls Nothing fancy..

1. Create a cache: Initialize an array memo of size n+1 to store the number of ways for each sum from 0 to n. Initially, all values are set to an indicator like null or -1 to show they haven't been computed yet.
2. Check the cache: Before performing any calculation for a sum k, check if memo[k] already has a value. If it does, return that stored value immediately.
3. Compute and store: If the value is not in the cache, compute it using the recursive formula ways(k) = ways(k-1) + ways(k-2). Once computed, store the result in memo[k] before returning it.

This ensures that each subproblem (ways(0), ways(1), ..., ways(n)) is solved only once.

Pseudocode for Memoization:

function ways(n):
    memo = array of size n+1, initialized to -1
    return dp(n, memo)

function dp(k, memo):
    if k == 0 or k == 1:
        return 1
    if memo[k] != -1:
        return memo[k]  // Return cached result

    result = dp(k-1, memo) + dp(k-2, memo)
    memo[k] = result  // Cache the result
    return result

Time Complexity: O(n) — We solve each of the n subproblems exactly once. Space Complexity: O(n) — For the memo array and the recursion call stack Not complicated — just consistent..

This changes depending on context. Keep that in mind That's the part that actually makes a difference..

Approach 2: Bottom-Up with Tabulation

The bottom-up approach is often more intuitive and avoids the overhead of recursion. Instead of starting from n and working backwards, we start from the smallest subproblems and build our way up to n.

1. Create a DP table: Initialize an array dp of size n+1.
2. Set base cases: We know the answers for the smallest problems. Set dp[0] = 1 and dp[1] = 1.
3. Fill the table iteratively: For each index i from 2 to n, calculate dp[i] using the values already computed in the table: dp[i] = dp[i-1] + dp[i-2].
4. Return the result: The value dp[n] is our final answer.

This method is like building a ladder from the ground up; you don't need to look back at the "call stack" because all previous steps are solidly in place Not complicated — just consistent..

Pseudocode for Tabulation:

function ways(n):
    if n == 0: return 1
    dp = array of size n+1
    dp[0] = 1
    dp[1] = 1

    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

Time Complexity: O(n) — A single loop from 2 to n. Space Complexity: O(n) — For the dp array.

Optimizing Space Complexity

We can further optimize the bottom-up approach. Notice that to calculate dp[i], we only need the two previous values: dp[i-1] and dp[i-2]. We don't need the

...entire history of steps stored in the array. We can replace the dp array with just two variables to track the previous two counts.

Pseudocode for O(1) Space:

function ways(n):
    if n == 0 or n == 1:
        return 1

    prev2 = 1  // Represents ways(i-2), initially ways(0)
    prev1 = 1  // Represents ways(i-1), initially ways(1)
    current = 0

    for i from 2 to n:
        current = prev1 + prev2
        prev2 = prev1      // Shift window forward
        prev1 = current

    return prev1

Time Complexity: O(n) — The loop still runs n times. Space Complexity: O(1) — We only use a constant number of variables regardless of input size That's the whole idea..

This is the optimal solution for the standard problem constraints. It mirrors the iterative Fibonacci calculation perfectly, demonstrating that the "Climbing Stairs" problem is fundamentally a Fibonacci sequence in disguise.

Summary of Approaches

Conclusion

The journey from a naive recursive solution to an O(1) space iterative approach encapsulates the core philosophy of Dynamic Programming: identify overlapping subproblems and eliminate redundant work.

We started with a mathematical definition that was computationally disastrous, introduced a cache to trade space for time (Memoization), restructured the computation flow to remove recursion overhead (Tabulation), and finally recognized the minimal state required to propagate the solution forward (Space Optimization).

Counterintuitive, but true.

This pattern—Recursion → Memoization → Tabulation → State Compression—is a universal framework applicable to a vast array of DP problems, from the Knapsack problem and Longest Common Subsequence to complex grid traversals and string editing distances. Mastering this progression on the "Climbing Stairs" problem provides the mental scaffolding required to tackle far more complex optimization challenges with confidence.