DP & BFS clear java solution


  • 0
    H
    //DP solution:
    public class Solution {
        public int numSquares(int n) {
            if (n < 0) return 0;
            int[] p = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                int min = n;
                for (int j = 1; j * j <= i; j++) {
                    min = Math.min(min, p[i - j * j] + 1); 
                }
                p[i] = min;
            }
            return p[n]; 
        }
    }
    
    //BFS
    public class Solution {
        public int numSquares(int n) {
            if (n < 1) return -1;
            Deque<Integer> q = new ArrayDeque<>();
            q.add(n);
            int ret = 0;
            while (!q.isEmpty()) {
                ret++;
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    int cur = q.poll();
                    int sr = (int) Math.sqrt(cur);
                    for (int j = sr; j > 0; j--) {
                        int delta = cur - j * j;
                        if (delta == 0) return ret;
                        q.offer(delta);
                    }
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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