3
\$\begingroup\$

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

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Neil Jul 19 '17 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.