I was able to come up with recursive approach . This is the approach. But it is getting me tle despite memoization.
Starting point:
Start with an empty string positioned at zero
Base case:
Return 1 when the current position i, becomes equals to n
Recursive cases:
a. If the previous character in the string is one then simply take zero for the next recursive call. As choosing zero would result in two adjacent ones.
b. If the previous character in the string is zero, then we can choose both zero and one making recursive calls to them.
Ending point:
I am trying to return the number of leaf nodes in the recursive tree which are able to reach at the level n.
Issue:
I assume the recursive solution works fine. But when I try to memoize it, somehow I am unable to keep a track of the unique states.
Brute force solution:
ll countWays(ll n, ll i, ll prev) {
if(i == n) {
return 1LL;
}
int takeOne = 0LL, takeZero = 0LL;
if(!prev) {
takeOne = countWays(n, i+1LL, 1LL);
}
takeZero = countWays(n, i+1LL, 0LL);
return takeOne + takeZero;
}
void solve(){
int n;
cin >> n;
//If the last character was a one, take zero only for the current position
//If the last character was a zero, take zero and one both for the current position
cout << countWays(n, 1LL, 0LL) + countWays(n, 1LL, 1LL) << endl;
}
Optimized Solution:
ll countNumbers(vector &dp, ll n, ll i, ll prev) {
if(i == n) return 1LL;
if(dp[i] != -1LL) {
return dp[i];
}
ll takeOne = 0LL, takeZero = 0LL;
if(prev == 0LL) {
takeOne = countNumbers(dp, n, i+1LL, 1LL);
}
takeZero = countNumbers(dp, n, i+1LL, 0LL);
return dp[n] = takeOne + takeZero;
}
void solve(){
ll n;
cin >> n;
vector <ll> dp(n+1LL, -1);
cout << countNumbers(dp, n, 1LL, 0LL) + countNumbers(dp, n, 1LL, 1LL) << endl;
}