2ms Java recursion + memo (beat 99.50%)


  • 0
    T

    There are two points to enhance performance.
    Basically to improve performance of DP, we should reduce execution time of solving subproblems.
    So, I focused on how to reduce loop count in recursion.(loop in rec function)

    1. Dividing point is alway bigger than mid of low and high. So, the loop can end when meet mid point. (-> reduce execution time by 1/2.)

    2. We should always choose lower number when we guess between two numbers.
      So, when there are n number (1,2,3,....n), we just need to choose n - 1(not n), n - 3(not n-2), n - 5(not n - 4)...
      So we can skip n, n - 2, n - 4....etc. (-> reduce execution time by 1/2.)

    So total execution time reduces to 1/4.

    public class Solution {
        int[][] dp;
        public int getMoneyAmount(int n) {
            dp = new int[n + 1][n + 1];
            return rec(1, n); 
        }
    
        private int rec(int lo, int hi) {
            if (lo >= hi) return 0;
            if (hi == lo + 1) return lo;
            if (dp[lo][hi] > 0) return dp[lo][hi];
            int minCost = Integer.MAX_VALUE, mid = (lo + hi) >> 1;
            for (int i = hi - 1; i >= mid; i -= 2) {
                minCost = Math.min(minCost, i + Math.max(rec(lo, i - 1), rec(i + 1, hi)));
            }
            return dp[lo][hi] = minCost;
        }
    }
    

  • 0
    P

    What would be the time complexity?

    According to me, if we do just plain recursion (without memoization) it shoud be O(n^n).
    With memoization, O(n^2) as there can be at most n*n different combinations to be found.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.