Pell Numbers
The Pell numbers start with P(0) = 0 and P(1) = 1. Every later one is twice the number before it plus the number before that: P(n) = 2 * P(n - 1) + P(n - 2).
So the sequence begins 0, 1, 2, 5, 12, 29. Return P(n).
Example 1
n 4
returns 12
P(4) = 2 * P(3) + P(2) = 2 * 5 + 2.
Example 2
n 1
returns 1
The second starting value.
Example 3
n 2
returns 2
P(2) = 2 * 1 + 0.
Constraints
0 <= n <= 30
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Savings With InterestBeginner
- Stacked CansBeginner
- Sum of the Last kBeginner
- Take One, Two or ThreeBeginner
- Three Button CalculatorBeginner
- Broken StairsEasy
- Cheapest Toll RouteEasy
- Evenly Spaced RunsEasy