动态规划ing-完全平方数｜Go主题月-一一网

【Golang主题学习月】周末肝了几道动态规划题，发了一个超细腻的教学版，反响很不错哦，接下来我会使用两种语言进行编码刷题，分别是GO和JAVA，各位菁英们，坚持刷题吧。

$\color{red}{如果你对动态规划不熟悉，望转到该篇~}$

肝了好多天-动态规划十连-超细腻解析｜刷题打卡

$\color{green}{这是一道比较简单的题目? ? ? ~}$

什么题可以选择动态规划来做？

1.计数

有多少种方式走到右下角
有多少种方法选出k个数是的和是sum

2.求最大值最小值

从左上角走到右下角路径的最大数字和
最长上升子序列长度

3.求存在性

取石子游戏,先手是否必胜
能不能选出k个数使得和是sum

4.综合运用

动态规划 + hash
动态规划 + 递归
…

leecode 279. 完全平方数

给定正整数 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

提示：

1 <= n <= $10^4$

—

❤️❤️❤️❤️

2.1. 动态规划组成部分1：确定状态

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似数学题中x, y, z代表什么

最后一步

如果n = 81 , 那么最坏的情况需要的和就是n次，相当于n个1相加

最好的情况就是1次，只需要一个完全平方数,我们可以用数组存下来，例如d[5] = d[4] + 1

我们定义d[n] 为和为 n 的完全平方数的最少数量

由题意， $x^2 + y^2 = n$ —> $n – y^2 >= 0$

很明显，y从1开始，直到 $n – y^2 >= 0$ , 用上面的例子来说在 $n – y^2 < 0$ 的前一步，当y自增到满足条件的最大值就是最后一步。

例如： $d[5] = 5 -2^2$ , 当y = 2, n = 5 时就是最后一步，我们只需要计算d[5] 和d[4] + 1的值就行了。

1.2. 动态规划组成部分2：转移方程

d[n] = min{d[n], d[n – y^2] + 1}

1.3. 动态规划组成部分3：初始条件和边界情况

初始化都为0次。

1.4. 动态规划组成部分4：计算顺序

每个n去匹配y。 (y的范围为1到 n – y^2 )

时间复杂度：n * n的平方根

空间复杂度：n，使用了一个一维数组 dp。

$\color{green}{棒！? ? ? ~}$

参考代码

GO语言版

func numSquares(n int) int {
    dp:=make([]int,n+1) // 默认初始化值都为0
    for i:=1;i<=n;i++{
        dp[i]=i     //最坏的情况就是每次+1
    }
    for i:=2;i<=n;i++{
        for j:=0;j*j<=i;j++{
            dp[i]=Min(dp[i],dp[i-j*j]+1)       
        }                                       
    }
    return dp[n]
}

func Min(a,b int)int{
    if a<b{
        return a
    }else{
        return b
    }
}





复制代码

$\color{red}{NICE太简单啦? ? ? ~}$

java版

    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }


复制代码