【动态规划】Leetcode 279. 完全平方数【中等】

本文主要是介绍【动态规划】Leetcode 279. 完全平方数【中等】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

解题思路

1、使用动态规划求解，定义一个一维数组dp，其中dp[i]表示和为i的完全平方数的最少数量。
2、初始化数组dp，长度为n + 1，全部初始化为最大值，dp[0]为0。
3、对于每个数字i，遍历从1到sqrt(i)的完全平方数j*j，更新dp[i]为dp[i - j * j] + 1和dp[i]中的较小值。
动态规划的状态转移方程为：
```
  dp[i] = min(dp[i], dp[i - j * j] + 1)，其中 1 <= j * j <= i
```
这个方程的意思是，如果当前的数 i 可以由 j * j 和 i - j * j 组成，那么 dp[i] 就可以通过 dp[i - j * j] + 1 来更新，即将 j * j 加入到和为 i 的完全平方数的组合中。
4、最终返回dp[n]即可。

Java实现

public class PerfectSquares {public int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;/*** 首先，定义一个数组 dp[]，其中 dp[i] 表示组成数值 i 的最小平方数数量。** 然后，通过两层循环遍历所有可能的数值 i，从 1 到 n。** 内层循环中，对于当前数值 i，我们尝试找到组成它的最小平方数数量。* 我们遍历所有小于等于 i 的平方数，记为 j * j，并更新 dp[i] 的值为* dp[i - j * j] + 1 的最小值。也就是说，我们找到了一个平方数 j * j，* 并尝试用它去更新 i 的最小平方数数量，看是否可以得到更优的解。** 最终，当外层循环结束时，dp[n] 中存储的就是组成数值 n 的最小平方数数量。* 这种解法的核心思想是利用动态规划的思想，* 通过计算子问题的最优解来构建更大规模问题的最优解。* 通过从小到大的顺序计算所有可能的数值 i，我们可以确保在计算 dp[i] 时，* dp[i - j * j] 已经计算过了，并且存储了正确的结果，* 从而确保每个状态的最优解被正确计算出来。*/for (int i = 1; i <= n; i++) {for (int j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}public static void main(String[] args) {PerfectSquares ps = new PerfectSquares();int n = 12;System.out.println("Minimum number of perfect squares: " +ps.numSquares(n)); // Output: 3 (12 = 4 + 4 + 4)}
}