Recursive dynamic programmic solution. O(n) space complexity


  • 0
    K

    Recursive dynamic programmic solution. O(n) space complexity

    public class Solution {
        int[] dp;
        List<Integer> squares;
        public int numSquares(int n) {
            dp = new int[n + 1];
            Arrays.fill(dp, -1);
            squares = new ArrayList<>();
            for(int i = 1; i * i <= n; i++) {
                squares.add(i * i);
            }
            return solve(n);
        }
        private int solve(int n) {
            if(n == 0) {
                return 0;
            }
            if(dp[n] != -1) {
                return dp[n];
            }
            int ans = Integer.MAX_VALUE;
            for(Integer s : squares) {
                if(s <= n) {
                    ans = Math.min(ans, solve(n - s) + 1);
                } else {
                    break;
                }
            }
            dp[n] = ans;
            return ans;
        }
    }
    

  • 0
    E

    Your program with failed when n is large enough.


Log in to reply
 

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