279. Perfect Squares

Leetcode link

题目简介

/**
 * @param {number} n
 * @return {number}
 */

题目给我们一个数字 n

要求我们求出 n 最少可以用多少个平方数之和来表示

平方数代表可以开根号为整数的数

解题思路

这题可以分成两个部分：

1. 首先找出所有小于等于 n 的平方数，把这些平方数的值当成一个个硬币
2. 用 322 题的思路来解

我们可以用一个数组 dp 来保存当前数字所需要用到的 “硬币” 数量，其状态转移方程为：

dp[i] = min(dp[i], dp[i-numSquare] + 1)

• 如果选择了 dp[i] 代表我们不用这个硬币

• 如果选择了 dp[i-numSquare] + 1 代表我们使用这个硬币

• 初始条件为 dp[0] = 0 如果数字为 0，我们不需要任何硬币

我们通过 i 从 1 到 n 的遍历就可以求出我们最少需要多少个 “硬币” 了

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
    const dp = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER)
    dp[0] = 0

    for (let i = 1; i <= n; i++) {
        for (let num = 1; num * num <= i; num++) {
            // we have 2 choices:
            // 1. use this square, then we should use dp[i-numSquare] + 1 number
            // 2. not to use this square, then we should use dp[i] number
            dp[i] = Math.min(dp[i], dp[i - num * num] + 1)
        }
    }

    return dp[n]
};