I worked on a dynamic programming problem. Here is its link. I have to find the number of ways respecting the constraint that user doesn't go to the Gym for two consecutive days.
public int numWays(int n) {
int[] DP = new int[n + 1];
DP[0] = 0;
DP[1] = 2;
DP[2] = 3;
for (int i = 3; i <= n; i++) {
DP[i] = DP[i - 1] + DP[i - 2];
}
return DP[n];
}
My solution works, however in case of n is very large, my solution won't perform good as its time complexity is exponential. I want to use matrix multiplication like the one for Fibonacci solution but Then I thought that it won't work exactly like that.
How can I improve my solution to have time complexity O(logn)?