ChunNote
0%

leetCode-279:Perfect Squares

发表于 分类于

问题描述

给定一个正整数，存在一些完全平方数的和等于这个正整数，要求找出数量最小的完全平方数的个数。题目链接：**点我**

样例输入输出

输入：12

输出：3

解释：12 = 4 + 4 + 4

输入：13

输出：2

解释：13 = 4 + 9

问题解法

使用动态规划进行求解，用 dp[n] 表示构成的 n 的完全平方数的最小数量，动态转移方程为 dp[n] = min(dp[n], dp[n - i * i])，其中 1 <= i * i <= n。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
    public int numSquares(int n)
    {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++)
            {
                dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            }
        }

        return dp[n];
    }
}