Untitled
unknown
plain_text
2 months ago
582 B
2
Indexable
class Solution { int[] dp = new int[100000]; int Modd = (int)(1e9 + 7); public int countHousePlacements(int n) { Arrays.fill(dp, -1); int x = solve(0, n); // Already modded in solve return (int)((1L * x * x) % Modd); // Prevent overflow during squaring } public int solve(int idx, int n) { if (idx >= n) return 1; if (dp[idx] != -1) return dp[idx]; int option1 = solve(idx + 1, n); int option2 = solve(idx + 2, n); return dp[idx] = (option1 + option2) % Modd; } }
Editor is loading...
Leave a Comment