LeetCode: 279. 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.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

解题思路 —— 动态规划

记 dp[i] 为数字 i 的 the least number of perfect square numbers。
则 dp[i] = min(dp[i-j]+dp[j]), 其中，j 取 [1, i]。

AC 代码

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp{0, 1};
        
        for(int i = 2; i <= n; ++i)
        {
            dp.push_back(i);
            int sqrti = sqrt(i);
            if(sqrti*sqrti == i)
            {
                dp[i] = 1;
                continue;
            }
            for(int j = 1; j < i; ++j)
            {
                dp[i] = min(dp[i], dp[j]+dp[i-j]);
            }
        }
        
        return dp[n];
    }
};