Description:

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

Example:

Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9

Link:

http://www.lintcode.com/en/problem/perfect-squares/

題目意思：

給出一個正整數(shù)n，求這個正整數(shù)最小可以由幾個平方數(shù)相加而成。

解題方法：

使用dp來解題，創(chuàng)建一個size為n+1的數(shù)組來儲存從1~n的每個數(shù)的題解（平方數(shù)則為1）。
狀態(tài)轉移方程為dp[n] = min(dp[i] + dp[n-i])

Tips:

for(int j = 1; j*j <= i/2; j++) result[i] = result[i] > result[j*j] + result[i-j*j] ? result[j*j] + result[i-j*j] : result[i];
將j換成了j*j，是可以跳過一些不是平方數(shù)的數(shù)字，如果不換的話Lintcode時間報錯但是leetcode可以AC。

Time Complexity：

當把j換成了j*j后，時間復雜度為O(nlogn)，否則為O(n^2)。
空間復雜度為O(n)。

完整代碼：

int numSquares(int n) { if(n < 1) return 0; vector<int> result(n+1, INT_MAX); for(int i = 1; i*i <= n; i++) result[i*i] = 1; for(int i = 2; i <= n; i++) { if(result[i] == INT_MAX) for(int j = 1; j*j <= i/2; j++) result[i] = result[i] > result[j*j] + result[i-j*j] ? result[j*j] + result[i-j*j] : result[i]; } return result[n]; }