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

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

image.png

一個(gè)耗時(shí)較高，內(nèi)存占用較大的一個(gè)解法：

package dynamic.program;


import java.util.ArrayList;
import java.util.List;

/**
 * 動(dòng)態(tài)規(guī)劃
 *
 * @author mingtong.zk
 * @version : P279PerfectSquares.java, 2020年04月06日 8:42 PM v 0.1  mingtong.zk Exp $
 **/
public class P279PerfectSquares {

    /**
     * Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
     *
     * Example 1:
     *
     * Input: n = 12
     * Output: 3
     * Explanation: 12 = 4 + 4 + 4.
     * Example 2:
     *
     * Input: n = 13
     * Output: 2
     * Explanation: 13 = 4 + 9.
     */
    public static void main(String[] args) {
        P279PerfectSquares p = new P279PerfectSquares();
        List<Integer> perfectSquares = p.findPerfectSquares(13);

        System.out.println(perfectSquares);

        System.out.println(p.numSquares(24));
    }

    int[] tmp;
    public int numSquares(int n) {
        tmp = new int[n+1];
        for (int i = 0; i < n+1; i++) {
            tmp[i] = Integer.MAX_VALUE;
        }
        List<Integer> perfectSquares = findPerfectSquares(n);
        return digui(n, perfectSquares);
    }

    // 計(jì)算數(shù)字n 可以拆解成哪些數(shù)字的和
    private int digui(int n, List<Integer> perfectSquares) {

        if (tmp[n] != Integer.MAX_VALUE) {
            return tmp[n];
        }
        if (perfectSquares.contains(n)) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        for (int i = perfectSquares.size() - 1; i >= 0 ; i--) {
            if (perfectSquares.get(i) <= n) {
                min = Math.min(min, 1 + digui(n - perfectSquares.get(i), perfectSquares));
            }
        }
        tmp[n] = min;
        return min;
    }

    // 尋找 < n 的所有的可以計(jì)算平方的那些數(shù)字,1,4,9,16,...
    private List<Integer> findPerfectSquares(int n) {
        List<Integer> squarLists = new ArrayList<>();
        if (n == 1) {
            squarLists.add(1);
            return squarLists;
        }
        for (int i = 1; i <= n / 2; i++) {
           if (i * i <= n) {
               squarLists.add(i * i);
           } else {
               break;
           }
        }
        return squarLists;
    }

}

這個(gè)方法一開(kāi)始就去尋找總共有哪些平方數(shù)，耗時(shí)較大

image.png

修改一下遞歸方式：

package dynamic.program;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 動(dòng)態(tài)規(guī)劃
 *
 * @author mingtong.zk
 * @version : P279PerfectSquares.java, 2020年04月06日 8:42 PM v 0.1  mingtong.zk Exp $
 **/
public class P279PerfectSquaresV2 {

    /**
     * Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
     *
     * Example 1:
     *
     * Input: n = 12
     * Output: 3
     * Explanation: 12 = 4 + 4 + 4.
     * Example 2:
     *
     * Input: n = 13
     * Output: 2
     * Explanation: 13 = 4 + 9.
     */
    public static void main(String[] args) {
        P279PerfectSquaresV2 p = new P279PerfectSquaresV2();
        System.out.println(p.numSquares(13));
    }
    public int numSquares(int n) {
        int[] tmp = new int[n+1];
        Arrays.fill(tmp, Integer.MAX_VALUE);
        return digui(n, tmp);
    }

    // 計(jì)算數(shù)字n 可以拆解成哪些數(shù)字的和
    private int digui(int n, int[] tmp) {

        if (n == 0) {
            return  0;
        }
        if (tmp[n] != Integer.MAX_VALUE) {
            return tmp[n];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1;  n - i * i >= 0 ; i++) {
            min = Math.min(min, 1 + digui(n - i * i, tmp));
        }
        tmp[n] = min;
        return tmp[n];
    }


}

耗時(shí)降低了

image.png

轉(zhuǎn)換成動(dòng)態(tài)規(guī)劃方式：自底向上

package dynamic.program;


import java.util.Arrays;

/**
 * 動(dòng)態(tài)規(guī)劃
 *
 * @author mingtong.zk
 * @version : P279PerfectSquares.java, 2020年04月06日 8:42 PM v 0.1  mingtong.zk Exp $
 **/
public class P279PerfectSquaresV3 {

    /**
     * Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
     *
     * Example 1:
     *
     * Input: n = 12
     * Output: 3
     * Explanation: 12 = 4 + 4 + 4.
     * Example 2:
     *
     * Input: n = 13
     * Output: 2
     * Explanation: 13 = 4 + 9.
     */
    public static void main(String[] args) {
        P279PerfectSquaresV3 p = new P279PerfectSquaresV3();
        System.out.println(p.numSquares(24));
    }
    public int numSquares(int n) {
        int[] tmp = new int[n+1];
        Arrays.fill(tmp, Integer.MAX_VALUE);
        return dp(n, tmp);
    }

    // 計(jì)算數(shù)字n 可以拆解成哪些數(shù)字的和
    private int dp(int n, int[] dp) {

        dp[0] = 0;
        dp[1] = 1;

        // 計(jì)算數(shù)字i 的最小乘積個(gè)數(shù)
        for (int i = 1; i <= n; i++) {
            // 拆解為 j,  i - j * j
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
            }
        }
        return dp[n];
    }

}

耗時(shí)如下：

image.png