算法记录

LeetCode 题目：

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

&emsp;&emsp;完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明

一、题目

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

二、分析

存在最小的优解，那么我们不妨使用动态规划来套一下，如果当前的数本身就是一个完全平方数，那么当前数的个数就为 1。

如果说当前数可以拆分由两个完全平方数之和，那么当前数的个数就为 2。

以此就可以将一个大问题拆分到小问题身上了，最小的单位就是 1，本身就是一个完全平方数。

class Solution {    public int numSquares(int n) {        int[] dp = new int[n + 1];        for(int i = 1; i <= n; i++) {            int min = i;            for(int j = 1; j * j <= i; j++) {                min = Math.min(min, dp[i - j * j]);            }            dp[i] = min + 1;        }        return dp[n];    }}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

动态规划。

原文：https://juejin.cn/post/7103868913779212296