Recursion to DP in Java


  • 0
    L

    I tried a top-down DP using recursion but got the TLE. Following code shows the recurrence relationship:

    private int helper(int i, int n, int[] dp)
      {
        if (n <= 0)
        {
          return 0;
        }
        if (n == 1)
        {
          return 1;
        }
        if (dp[n] != -1)
        {
          return dp[n];
        }
        int min = n;
        for (int j = i; j  <= Math.sqrt(n); j++)
        {
          min = Math.min(min, 1
              + Math.min(helper(j, n - j * j, dp),
                  1 + helper(j + 1, n, dp)));
        }
        dp[n] = min;
        return min;
      }
    

    Another try was to use a bottoms-up DP approach that will use O(n^2) time complexity:

     public int helper_dp(int n) {
           int[] DP = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                int min= Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++)
                {
                    min= Math.min(min, DP[i - j * j] + 1);
                }
                DP[i] = min;
            }
            return DP[n];
        }
    

Log in to reply
 

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