Number factors

Counting the number of ways to write n as an ordered sum of 1s, 3s, and 4s is solved by recognizing that the last term of any valid sequence is either 1, 3, or 4 — so the count for n is the sum of the counts for the three smaller sub-problems that remain after removing that last term, turning a combinatorial explosion into a linear recurrence.

Recognize the pattern

• Question asks for the number of ways / count of sequences, not the sequences themselves (if it asked to list them, you'd need backtracking, not DP).
• The sum is ordered (compositions, not partitions) — {1,3} and {3,1} both count. That's the tell that the recurrence sums over "last move" choices, like climbing stairs.
• A fixed, small set of "moves" (1, 3, 4) that combine additively toward a target — same shape as Coin Change (count ways), Climbing Stairs, and Fibonacci/Tribonacci.

Brute force → optimal

Brute force (recursion tree): define countWays(n) = countWays(n-1) + countWays(n-3) + countWays(n-4) with base cases countWays(0)=1, countWays(neg)=0. Each call branches into 3 more, and subproblems like countWays(n-4) get recomputed via many different paths (e.g. reaching 6 via n-1-1-4 and n-4-1-1 both hit countWays(2) repeatedly). That gives a call count that is exponential and impractical past n≈30.

Optimal (bottom-up DP): notice the recursion only ever needs the previous 4 values of n. Build a table dp[0..n] left to right, each entry computed once in O(1) from three earlier entries. That collapses the exponential tree into O(n) time, and can be reduced to O(1) extra space by keeping only the last 4 values in rolling variables.

Complexity, derived

Brute force call count T(n) = T(n-1)+T(n-3)+T(n-4)+O(1) is bounded above by the ternary recursion T(n) ≤ 3·T(n-1), giving the loose worst-case bound T(n) = O(3^n). This is a bound on how many calls the naive recursion makes, not on the size of the answer — it's loose because it ignores that many of those calls are duplicates. Space for the call stack is O(n).

The dp values themselves grow at a different, slower rate: dp(n) satisfies the same recurrence dp(n)=dp(n-1)+dp(n-3)+dp(n-4), whose characteristic polynomial x⁴=x³+x+1 has dominant real root exactly φ (the golden ratio, ≈1.618) — check: φ²=φ+1 ⇒ φ³=φ·φ²=φ²+φ=2φ+1 ⇒ φ⁴=φ·φ³=2φ²+φ=2(φ+1)+φ=3φ+2, and φ³+φ+1=(2φ+1)+φ+1=3φ+2, so the identity holds exactly. So dp(n) = Θ(φ^n) ≈ Θ(1.618^n) — a much smaller number than the O(3^n) call-count bound above; the two describe different things (work done vs. size of the result) and shouldn't be conflated.

DP table: n+1 entries, each filled in constant time by one addition of three lookups → time is exactly (n+1)·O(1) = O(n). The full table costs O(n) space; since dp[i] only depends on dp[i-1..i-4], a 4-slot rolling window suffices → O(1) space.

Traced example: n = 5

dp[5] = 6 matches the 6 orderings {1,1,1,1,1}, {1,1,3}, {1,3,1}, {3,1,1}, {1,4}, {4,1}.

Pitfalls

• Wrong base cases: forgetting dp[0]=1 (the empty composition) makes every downstream value off; forgetting negative indices resolve to 0 causes array-index-out-of-bounds if implemented with raw array lookups instead of guards.
• Confusing with unordered partitions: if the problem meant "how many multisets of 1/3/4 sum to n" (order doesn't matter), the recurrence and table dimensionality change completely (it becomes a coin-change-style 2D DP over which denominations are allowed).
• Overflow: dp(n) grows like φ^n ≈ 1.618^n (see derivation above), and 2^63 ≈ (1.618)^91, so for long in Java, overflow becomes a real concern once n climbs beyond roughly 90 — switch to BigInteger past that point.

When to use / when not

Use bottom-up DP with a rolling window whenever the answer for n depends on a small, fixed number of previous answers and you only need the count/optimum, not every sequence. Space drops from O(n) to O(1) for free.

vs. plain memoized recursion (top-down): same O(n) time and correctness, easier to write when the recurrence isn't obvious, but pays call-stack overhead and O(n) space for memo + stack — prefer bottom-up once the recurrence is settled and n can be large.

vs. matrix exponentiation: if n is huge (10^9) and only the final count is needed, express the recurrence as a 4x4 transition matrix and compute M^n in O(log n) time — worth it only when linear O(n) is actually too slow.

Java

class Solution {
    long countWays(int n) {
        if (n < 0) return 0;
        long[] dp = new long[Math.max(n + 1, 1)];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            long ways = dp[i - 1];
            ways += (i - 3 >= 0) ? dp[i - 3] : 0;
            ways += (i - 4 >= 0) ? dp[i - 4] : 0;
            dp[i] = ways;
        }
        return dp[n];
    }
}

O(1)-space rolling version keeps only the last four long values instead of the array.

Takeaways

• Ordered sum-to-target with a fixed move set → recurrence sums over the choice of last move.
• Recursion tree recomputes shared subproblems; DP fixes that by computing each subproblem exactly once, bottom-up.
• When each state depends on only a constant window of prior states, drop the full table for O(1) space.
• Don't conflate the recursion's call-count bound (O(3^n), a bound on work) with the growth rate of the answer itself (Θ(φ^n) ≈ Θ(1.618^n), the size of the result) — they answer different questions.

Recall: why is dp[0] = 1 the correct base case rather than 0?

Synthesized from the classic "count ways to express n as sum of 1, 3, 4" DP problem (AlgoDaily/GeeksforGeeks family); recurrence and complexity analysis (including the φ root of x⁴=x³+x+1) re-derived and checked by hand.