传送门：https://leetcode-cn.com/problems/perfect-squares/

题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 _n_ 。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
**

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


示例 2：

输入：n = 13 输出：2 解释：13 = 4 + 9

解题思路：动态规划

设 dp[i] 含义为组成和为 i 的完全平方数的最少个数。

边界条件： dp[0]=0
初始化：dp[i]=i ，默认 i =1+1+1....+1 如 4 开始默认由 1+1+1+1 组成

求解 dp[i] 时，dp[0...i-1] 必然已计算出 。由 i=(i- j*j) + ( j*j ) 可知其所有的组合形式，其中 j=[0...(j_max*j_max <= i)] ，(i-j*j) 的组合最少个数是已知的就是 dp[i-j*j] 。(j*j) 个数就是1 ，因此我们只要在所有的组合中找出个数最小的即可 。

状态转移方程：
🚩[LeetCode]dp279 完全平方数 - 图1

复杂度分析

时间复杂度：🚩[LeetCode]dp279 完全平方数 - 图2 ，其中 sqrt 为平方根 。

空间复杂度：🚩[LeetCode]dp279 完全平方数 - 图3。

代码

我的代码

  1. public class Demo {
  2.     //动态规划 dp[i] i为完全平方和所需的最少个数 i=i-j*j+j*j
  3.     //状态转移：dp[i]=Math.min(dp[i],dp[i-j*j]+1);
  4.     public static int numSquares(int n) {
  5.         if(n==0)return 0;
  6.         int[]dp=new int[n+1];
  7.         for (int i = 1; i <= n; i++) {
  8.             dp[i]=i;//初始化默认最小为1+1...+1
  9.             for (int j = 0; j*j <= i; j++) dp[i]=Math.min(dp[i],dp[i-j*j]+1);//限制条件 i-j*j>=0
  10.         }
  11.         return dp[n];
  12.     }
  14.     public static void main(String[] args) {
  15.         System.out.println(numSquares(12));
  16.     }
  17. }