Google Interview Question
SDE1sCountry: United States
O(n) space and time using dp
#include <iostream>
using namespace std;
int FindWays(int n)
{
int dp[n+1][2];
dp[0][0] = 1;
dp[0][1] = 0;
dp[1][0] = 1;
dp[1][1] = 0;
dp[2][0] = 1;
dp[2][1] = 1;
dp[3][0] = 0;
dp[3][1] = 1;
for(int i=4; i<=n; i++)
{
dp[i][0] = dp[i-1][1] + dp[i-2][1] + dp[i-4][1];
dp[i][1] = dp[i-1][0] + dp[i-3][0] + dp[i-4][0];
}
return dp[n][0] + dp[n][1];
}
int main() {
cout<<FindWays(4);
}
O(n) time and space.
- Alex December 05, 2017