Thinking process - DP

What's the input? What's the output?

• input: a positive integer number
• output: the east number of perfect square numbers which sum to input

Give some examples

• n = 2 => 1+1 => 2
• n = 5 => 1 + 1 +... +1 or 1 + 4 => 2
• how do we know that we can use 4 here? because 5 is larger than 4

Similar to backpack, given a target value, how many items needed to fill exactly the backpack, use as less items as possible

Mistakes

Math.pow(a, b) return a double

Time complexity

O (n sqrt n)

public class Solution {
    public int numSquares(int n) {
        //validate input
        if (n <= 0) return 0;

        int[] dp = new int[n + 1];//dp[i], the least number of PSN sum to i
        dp[0] = 0;

        //init
        for (int i = 1; i < dp.length; ++i) {
            dp[i] = i;
        }

        int base = 2;
        while (base*base <= n) {
            for (int i = 1; i < dp.length; ++i) {
                if (i >= base*base) {
                    dp[i] = Math.min(dp[i], dp[i - base*base] + 1);
                }
            }

            base++;
        }

        return dp[n];

    }
}

Thinking process - DFS - Time Limit Exceed

Thinking Process - BFS

The basic idea of this solution is a BSF search for shortest path, from given input to 0

• how fast can we reach to 0?

When to increase level?

• using rightmost? integer, pass by value, no!!
• get the size before adding more!!!!

Mistakes

• BFS using queue instead of priorityqueue
• using ArrayDeque, otherwise got TLE
• primitive type, pass by value, so don't use right most strategy

API

ArrayDeque

https://discuss.leetcode.com/topic/40407/straightforward-java-bfs-beats-93-69/2

ArrayDeque is Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

Math

(int) Math.sqrt(12) => 3

(int) Math.sqrt(15) => 3

public class Solution {
    public int numSquares(int n) {
        //validate input
        if (n <= 0) return 0;

        int res = 0;
        Queue<Integer> q = new ArrayDeque<>();
        q.add(n);

        while (!q.isEmpty()) {
            int size = q.size();
            res++;
            for (int i = 0; i < size; ++i) {
                int num = q.remove();
                int base = (int)Math.sqrt(num);
                for (int j = base; j >= 1; --j) {
                    if (num - j*j == 0) return res;
                    q.offer(num - j*j);
                }
            }
        }

        return 0;
    }
}