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 =13Output: 2 Explanation:13 = 4 + 9.
按完全平方数来分割整数
C++：dp
1 class Solution { 2 public: 3 int numSquares(int n) { 4 if (n == 0) 5 return 0 ; 6 vector<int> squareList = getSquareList(n) ; 7 vector<int> dp(n+1 , 0) ; 8 for(int i = 1 ; i <= n ; i++){ 9 int minNum = n; 10 for(int square : squareList){ 11 if(square > i){ 12 break ; 13 } 14 minNum = min(minNum,dp[i-square] + 1) ; 15 } 16 dp[i] = minNum ; 17 } 18 return dp[n] ; 19 } 20 21 vector<int> getSquareList(int n) { 22 vector<int> squareList ; 23 int base = 1 ; 24 int diff = 1 ; 25 while(base <= n){ 26 squareList.push_back(base) ; 27 diff += 2 ; 28 base += diff ; 29 } 30 return squareList ; 31 } 32 };
原文：https://www.cnblogs.com/mengchunchen/p/10277463.html