Java DP O(n) space and O(n^1.5) runtime ?


  • 0

    For every integer i, iterate through all perfect square numbers m, from 1 to ~ sqrt(i), find the minimum of fewest[i - m * m] + 1. the i-mm term is smaller than i such is already computed.
    For for n, there are sqrt(n) such perfect numbers. The total runtime is n
    sqrt(n), which is n^1.5
    . I am not sure about the runtime accuracy. Anyone at good math gives a comment? Also, is there a better solution? Something like O(n) time or better, or O(1) space?

       public class Solution {
            public int numSquares(int n) {
                int[] fewest = new int[n + 1];
                fewest[0] = 0;
                int min;
                for (int i = 1; i <= n; i++) {
                    min = i;
                    for (int m = 1; m * m <= i; m++) {
                        min = Math.min(min, 1 + fewest[i - m * m]);
                    }
                    fewest[i] = min;
                }
                return fewest[n];
            }
        }

  • 0
    Z

    Yes, Dp solution is O(n^1.5) runtime, I am also searching better solution.


Log in to reply
 

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