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
