力扣——完全平方数

标题链接：

链接
标题描述：

思路：

用动态规划，设                                   i                              i                  i的最少数量是                                   d                         p                         (                         i                         )                              dp(i)                  dp(i)，最多数量是                                   i                              i                  i，如1+1+…+1
则                                        d                            p                            (                            i                            )                            =                            m                            i                            n                            {                            i                            ,                            d                            p                            (                            i                            −                            j                            ∗                            j                            )                            +                            1                            }                                  dp(i)=min\{ i,dp(i-j*j)+1 \}                     dp(i)=min{i,dp(i−j∗j)+1}
这里为什么是                                   d                         p                         (                         i                         −                         j                         ∗                         j                         )                         +                         1                              dp(i-j*j)+1                  dp(i−j∗j)+1，因为要得到                                   i                              i                  i减去一个平方数后的最小组成数量，那么                                   i                              i                  i的最小组成数量就是减去平方数后的最小组成数量+1，这个1就代表减去的这个平方数
实现代码：

• 
  

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

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。