279. Perfect Squares

using System;
public class Solution {
    public int NumSquares(int n) {
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        int maxSquareIndex = (int)Math.Sqrt(n) + 1;
        int[] squareNums = new int[maxSquareIndex];
        for (int i = 1; i < maxSquareIndex; ++i) {
            squareNums[i] = i * i;
        }
        
        for (int i = 1; i <= n; ++i) {
            for (int s = 1; s < maxSquareIndex; ++s) {
                if (i < squareNums[s]) break;
                dp[i] = Math.Min(dp[i], dp[i - squareNums[s]] + 1);
            }
        }
        
        return dp[n];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumSquares(int n) {
        vector<int>& dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        int maxSquareIndex = (int)Math.Sqrt(n) + 1;
        vector<int>& squareNums = new int[maxSquareIndex];
        for (int i = 1; i < maxSquareIndex; ++i) {
            squareNums[i] = i * i;
        }
        
        for (int i = 1; i <= n; ++i) {
            for (int s = 1; s < maxSquareIndex; ++s) {
                if (i < squareNums[s]) break;
                dp[i] = min(dp[i], dp[i - squareNums[s]] + 1);
            }
        }
        
        return dp[n];
    }
}

class Solution {

  public int numSquares(int n) {
    int dp[] = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    int max_square_index = (int) Math.sqrt(n) + 1;
    int square_nums[] = new int[max_square_index];
    for (int i = 1; i < max_square_index; ++i) {
      square_nums[i] = i * i;
    }

    for (int i = 1; i <= n; ++i) {
      for (int s = 1; s < max_square_index; ++s) {
        if (i < square_nums[s])
          break;
        dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
      }
    }
    return dp[n];
  }
}

var numSquares = function(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    const maxSquareIndex = Math.floor(Math.sqrt(n)) + 1;
    const squareNums = new Array(maxSquareIndex).fill(0).map((_, i) => i * i);
    
    for (let i = 1; i <= n; i++) {
        for (let s = 1; s < maxSquareIndex; s++) {
            if (i < squareNums[s]) break;
            dp[i] = Math.min(dp[i], dp[i - squareNums[s]] + 1);
        }
    }
    
    return dp[n];
};

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        max_square_index = int(n**0.5) + 1
        square_nums = [i * i for i in range(max_square_index)]
        
        for i in range(1, n + 1):
            for s in range(1, max_square_index):
                if i < square_nums[s]:
                    break
                dp[i] = min(dp[i], dp[i - square_nums[s]] + 1)
        
        return dp[n]

import (
    "math"
    "fmt"
)

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    
    maxSquareIndex := int(math.Sqrt(float64(n))) + 1
    squareNums := make([]int, maxSquareIndex)
    for i := 1; i < maxSquareIndex; i++ {
        squareNums[i] = i * i
    }
    
    for i := 1; i <= n; i++ {
        for s := 1; s < maxSquareIndex; s++ {
            if i < squareNums[s] {
                break
            }
            dp[i] = min(dp[i], dp[i-squareNums[s]]+1)
        }
    }
    
    return dp[n]
}

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

Algorithm

Инициализация:

Создайте tableau dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.

Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в tableauе square_nums.

Заполнение tableauа dp:

Для каждого числа i от 1 до n:

Для каждого совершенного квадрата s из tableauа square_nums:

Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.

Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

Возврат результата:

return значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎