动态规划-279. Perfect Squares

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

一个耗时较高，内存占用较大的一个解法：

package dynamic.program;


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

/**
 * 动态规划
 *
 * @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);
    }

    // 计算数字n 可以拆解成哪些数字的和
    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 的所有的可以计算平方的那些数字,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;
    }

}

这个方法一开始就去寻找总共有哪些平方数，耗时较大

image.png

修改一下递归方式：

package dynamic.program;


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

/**
 * 动态规划
 *
 * @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);
    }

    // 计算数字n 可以拆解成哪些数字的和
    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];
    }


}

耗时降低了

image.png

转换成动态规划方式：自底向上

package dynamic.program;


import java.util.Arrays;

/**
 * 动态规划
 *
 * @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);
    }

    // 计算数字n 可以拆解成哪些数字的和
    private int dp(int n, int[] dp) {

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

        // 计算数字i 的最小乘积个数
        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];
    }

}

耗时如下：

image.png