01 · Question
A one-story castle is one unit block. An n-story castle consists of two (n−1)-story castles side by side, separated by a one-unit gap, plus a solid roof row connecting them. For n ≥ 1, return the total number of blocks.
Examples: n=1 → 1; n=2 → 5; n=3 → 17; n=4 → 49. The Go result must fit int64 (1 ≤ n ≤ 57).
02 · Analysis
One state is insufficient to describe the new roof. Define width W and block count B: W(1)=B(1)=1, W(n)=2W(n−1)+1, and B(n)=2B(n−1)+W(n).
If B(n) separately recomputes W(n), W(n−1), and so on, the total work is n+(n−1)+…+1 = O(n²). The book memoizes widths to get O(n). The implementation below instead returns (blocks, width) together from one call, avoiding repeated work without a cache.
Each level makes one recursive call and combines two scalars: O(n) arithmetic operations and O(n) stack space under a fixed-width arithmetic model. Large exact Python answers have increasing bit lengths. An iterative version of the same paired recurrence can use O(1) scalar slots.