动态规划--完全平方数

算法

发布日期: 2021-04-19

更新日期: 2021-04-19

文章字数: 999

阅读时长: 4 分

阅读次数:

每天一道算法题解

题目

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

由于题目让求最值，是可以使用动态规划来解决。完全平方数是整数的平方，所以从小到大可以用 i*i （i=1，2，3...） 表示因为 n 是多个完全平方数的和，所以最大完全平方数一定不大于 n, 因此有 i*i<=n，根据这个关系可以得到一个有限的完全平方数的序列，用序列中的数拼凑 n。

既然是动态规划，我们按照3步走，找到题目问题的子问题，并得到状态转移方程，以及确定边界

确定子问题

因为题目要求和为 n 的完全平方数的最少数量，我们可以定义 dp[i] 表示可以拼凑成 i 的完全平方数的最少个数

确定状态转移方程

假设 n = 12, 可以得到可用完全平方数的序列为 [1, 4, 9], 即拼成12的最后一个完全平方数可以是三者其一，因此，有三种可能可以拼凑成12，他们完全平方数的个数分别是dp[12-1]+1、dp[12-4]+1和dp[12-9]+1, 要求最少的个数，就要对三者取min，即dp[12] = min(dp[12-1]+1, dp[12-4]+1, dp[12-9]+1)
那么，对于 dp[11] ，同样可以得到可用序列为 [1, 4, 9], 根据上面的推论，可以得到 dp[11] = min(dp[11-1]+1, dp[11-4]+1, dp[11-9]+1)
以此类推
我们可以得到状态转移方程 dp[i]= min(dp[i-k]+1)， k∈square numbers

确定边界

对于n=0，不需要平方数，即dp[0]=0，因为要求最小值，所以，dp[i] 均大于 n

算法实现

func numSquares(n int) int {
  // 确定最大平方数索引
  maxSquareIndex := int(math.Sqrt(float64(n))) + 1
  squares := make([]int, maxSquareIndex)
  // 列出所有可用的平方数
  for i := 1; i < maxSquareIndex; i++ {
    squares[i] = i * i
  }
  // 创建动态数组
  dp := make([]int, n+1)
  dp[0] = 0
  for i := 1; i <= n; i++ {
    dp[i] = n // 数组初始值设为 n，只要比 n 大都行
    for j := 1; j < maxSquareIndex; j++ {
      if i < squares[j] { // 平方数大于 i 则不可能拼凑 i
        break
      }
      // 求最小数量
      dp[i] = min(dp[i], dp[i-squares[j]]+1)
    }
  }
  return dp[n]
}

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

上面解法，平方数序列除了最后几次能用到全部，前几次都直接break了，所以可以将这部分放在计算时进行，优化如下

func numSquares(n int) int {
    dp := make([]int, n+1)
    dp[0] = 0
    for i := 1; i <= n; i++ {
        dp[i] = i // 数组初始化为最坏情况，即平方数全为 1 的情况
        for j := 1; j*j <= i; j++ { // 计算时比较平方数是否超出i
            dp[i] = min(dp[i], dp[i-j*j]+1)
        }
    }
    return dp[n]
}