# Number of ways to complete a plan

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)?

• I fail to see the problem with the matrix-based fibonacci solution linked. That has O(log n) time. It even has Java code to accomplish it. The only real difference in your case is that your n is the n+3th fibonacci number so you'll simply have to subtract 3 from n beforehand. – Neil Jul 19 '17 at 13:57