Longest Increasing Path in a Matrix

Question

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution

我太笨了，想不大到解法，所以直接看了解答。其實我應該更敏銳一點的，題目說了 least number，應該要想到用 DP 的三大時機：

1. maximum/ minimum 找最大或最小
2. yes/no 存不存在
3. counts 有多少方案

這題剛好符合第一個。決定要用 DP，最為困難的地方在於該如何找到 state function，這題的核心思想在，while (i - j² >= 0)，因為當這個 while 裡面的敘述是正確的，就代表存在 j 乘以 j 這樣的一個平方數存在，因此 dp[i] = Math.min(min, dp[i - j²] + 1)

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            int j = 1;
            while (i - j * j >= 0) {
                min = Math.min(min, dp[i - j * j] + 1);
                j++;
            }
            dp[i] = min;
        }
        return dp[n];
    }

其實在九章裡面也說過，要找到兩點之間的最短距離，也是透過 BFS。舉 12 為例，我們可以用一個 stack 來記錄 12，接著算出經過第一次減去比 12 小的平方數的結果 （這邊代表的含義就是 level 1），把這些點放進 stack 後再逐層往下。

    public int numSquares(int n) {
        if (n < 2) {
            return n;
        }

        List<Integer> numbers = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 1; i * i <= n; i++) {
            numbers.add(i);
        }
        stack.push(n);
        int len = 0;
        while (!stack.isEmpty()) {
            Stack<Integer> next = new Stack<Integer>();
            len++;
            int level = stack.size();
            for (int j = 0; j < level; j++) {
                int node = stack.pop();
                for (int i = 0; i < numbers.size(); i++) {
                    if (node - numbers.get(i) * numbers.get(i) > 0) {
                        next.push(node - numbers.get(i) * numbers.get(i));
                    } else if (node - numbers.get(i) * numbers.get(i) == 0) {
                        return len;
                    } else {
                        break;
                    }
                }
            }
            stack = next;
        }
        return len;
    }