Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.
For example, givenn=12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.
【題目分析】
一個(gè)數(shù)可以由一些完全平方數(shù)相加得到，例如1,4,9,16,...
給定一個(gè)數(shù)n，求出使得相加結(jié)果為n所需最少的完全平方數(shù)的個(gè)數(shù)。
【思路】
1. 遞歸
對(duì)于一個(gè)數(shù)，我們?cè)趺辞笏挠赡男┩耆椒綌?shù)相加得到的呢？
首先找到距離這個(gè)數(shù)最近的完全平方數(shù)m = x*x，我們從1~x中選擇一個(gè)數(shù)，求出n中包含z個(gè)x*x，我們?cè)谶f歸求出n-z*x*x所包含的完全平方數(shù)。遍歷1~x，返回其中最小的結(jié)果。
2. 動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃用 dp[i] 數(shù)組存儲(chǔ)第 i 個(gè)數(shù)的完美平方數(shù)。遞推式為：dp[i] = Math.min(dp[j] + dp[i-j], dp[i])，認(rèn)為 i 的完全平方數(shù)是從和為 i 的兩個(gè)完全平方數(shù) dp[j] 和 dp[i-j]之和，然后從中取最小。
?3. 改進(jìn)后的動(dòng)態(tài)規(guī)劃
任何數(shù)字都可以表示成為一個(gè)普通數(shù)字加上一個(gè)完全平方數(shù)，因此有如下表格：
任何數(shù)的表示形式
如圖所示，紅色部分表示平方數(shù)，所有的數(shù)都可以看做一個(gè)普通數(shù)加上一個(gè)完美平方數(shù)，那么遞推式就變?yōu)榱耍篸p[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。
java遞歸實(shí)現(xiàn)：
public class Solution {
? ? public int numSquares(int n) {
? ? ? ? int count = n;
? ? ? ? int nearest = (int)Math.sqrt(n);
? ? ? ? if(n == 0) return 0;
? ? ? ? if(nearest*nearest == n) return 1;
? ? ? ? for(int i = nearest; i >= 1; i--) {
? ? ? ? ? ? int cur = 0, num? = n, t = i*i;
? ? ? ? ? ? while(num - t >= 0) {
? ? ? ? ? ? ? ? num -= t;
? ? ? ? ? ? ? ? cur++;
? ? ? ? ? ? }
? ? ? ? ? ? if(cur < count){
? ? ? ? ? ? ? ? count = Math.min(numSquares(num)+cur, count);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return count;
? ? }
}
java 動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：
public class Solution {
? ? /*
? ? 動(dòng)態(tài)規(guī)劃的思想來(lái)解決，遞推公式dp[i] = Math.min(dp[j] + dp[i-j], dp[i])
? ? */
? ? public int numSquares(int n) {
? ? ? ? int[] array = new int[n+1];
? ? ? ? Arrays.fill(array, Integer.MAX_VALUE);
? ? ? ? array[1] = 1;
? ? ? ? for(int i = 2; i <=n; i++) {
? ? ? ? ? ? int sqr = (int)Math.sqrt(i);
? ? ? ? ? ? if(sqr*sqr == i) array[i] = 1;
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? for(int j = 1; j <= i/2; j++) {
? ? ? ? ? ? ? ? ? ? array[i] = Math.min(array[j]+array[i-j], array[i]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return array[n];
? ? }
}、
改進(jìn)的動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：
public class Solution {
? ? /*
? ? 改進(jìn)后動(dòng)態(tài)規(guī)劃，遞推公式dp[i+j*j] = Math.min(dp[i]+1, dp[i+j*j])
? ? */
? ? public int numSquares(int n) {
? ? ? ? int[] array = new int[n+1];
? ? ? ? Arrays.fill(array, Integer.MAX_VALUE);
? ? ? ? for(int i = 1; i*i <= n; i++) {
? ? ? ? ? ? array[i*i] = 1;
? ? ? ? }
? ? ? ? for(int i = 1; i <= n; i++) {
? ? ? ? ? ? for(int j = 1; i+j*j <= n; j++) {
? ? ? ? ? ? ? ? array[i+j*j] = Math.min(array[i]+1, array[i+j*j]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return array[n];
? ? }
}
