未分類

Perfect Squares

BreadthFirstSearch, DynamicProgramming, Go, LeetCode, Math

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.

For example:

1
2
3
Given n = 12, return 3 because 12 = 4 + 4 + 4;
Given n = 13, return 2 because 13 = 4 + 9.
提示 解題應用
DynamicProgramming 規律觀查

Default:

1
2
3
func numSquares(n int) int {
}

解答思路:

最初的想法本來是要先透過列出1~k的2次方，再來來做排列組合以找出總合n，不過這樣子不管怎麼改都太耗時間了，所以倒不如從1開始一路到n找最少有幾個平方數組成，最大的好處就是在找後面的數字像n時，由於已經知道1~n-1的結果了，因此在計算時好比n=12如下:

1
2
3
4
n=12
12 = 1x1 + 11 (1種組合+n=11的組合數)
   = 2x2 + 8  (1種組合+n=8的組合數)
   = 3x3 + 3  (1種組合+n=3的組合數)

此時就只要將每種組合(1)+先前所計算剩餘值的組合數(n減去該種組合的值)，最後找出何種組合的組合數最小就會是n的組合數。

程式碼解說:

一開始就初始化一個長度為n+1的陣列用來儲存1~n每個最少有幾個平方數組成，長度多1是因為之後可能會出現值為0的情況，因此該組合數就同樣也為0，接著便從1開始一路到n分別找出最少有幾個平方數組成，每次都先計算每種組合(1x1,2x2…)+先前所計算剩餘值的組合數(n減去該種組合的值)，再來找出何種組合的組合數最小(初始值為n表示由最多的平方數組成=全部都為1)就會是n的組合數，最後回傳陣列的最後一個值就會是我們要的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var tmp int
var min int
nums := make([]int, n+1)
nums[0] = 0
for i := 1; i <= n; i++ {
	min = i
	for j := 1; j*j <= i; j++ {
		tmp = nums[i-j*j] + 1
		if tmp < min {
			min = tmp
		}
	}
	nums[i] = min
}
return nums[n]

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func numSquares(n int) int {
	var tmp int
	var min int
	nums := make([]int, n+1)
	nums[0] = 0
	for i := 1; i <= n; i++ {
		min = i
		for j := 1; j*j <= i; j++ {
			tmp = nums[i-j*j] + 1
			if tmp < min {
				min = tmp
			}
		}
		nums[i] = min
	}
	return nums[n]
}

總結:

要找n最少是由幾個平方數組成，倒不如從1開始一路到n找最少有幾個平方數組成，最大的好處就是在找後面的數字像n時，由於已經知道1~n-1的結果了，此時就只要將每種組合(1)+先前所計算剩餘值的組合數(n減去該種組合的值)，最後找出何種組合的組合數最小就會是n的組合數。

分享到