• 原題鏈接🔗：完全平方數(shù)
• 難度：中等????

題目

給你一個整數(shù) n ，返回 和為 n 的完全平方數(shù)的最少數(shù)量 。

完全平方數(shù) 是一個整數(shù)，其值等于另一個整數(shù)的平方；換句話說，其值等于一個整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 3 和 11 不是。

示例 1：

輸入：n = 12
輸出：3
解釋：12 = 4 + 4 + 4
示例 2：

輸入：n = 13
輸出：2
解釋：13 = 4 + 9

提示：

1 <= n <= 10⁴

動態(tài)規(guī)劃

動態(tài)規(guī)劃（Dynamic Programming，簡稱DP）是一種在數(shù)學(xué)、管理科學(xué)、計算機科學(xué)、經(jīng)濟學(xué)和生物信息學(xué)等領(lǐng)域中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。動態(tài)規(guī)劃常常用于優(yōu)化問題，特別是那些具有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。

動態(tài)規(guī)劃的關(guān)鍵概念：

1. 重疊子問題：原問題可以分解為多個子問題，而這些子問題會重復(fù)出現(xiàn)多次。
2. 最優(yōu)子結(jié)構(gòu)：一個問題的最優(yōu)解包含其子問題的最優(yōu)解。
3. 無后效性：一旦某個狀態(tài)被確定，它就不受之后決策的影響。
4. 狀態(tài)轉(zhuǎn)移方程：描述了問題的狀態(tài)如何從先前的狀態(tài)轉(zhuǎn)移而來。

動態(tài)規(guī)劃的步驟：

1. 定義狀態(tài)：確定問題的狀態(tài)，通常用數(shù)組或變量來表示。
2. 確定狀態(tài)轉(zhuǎn)移方程：找出狀態(tài)之間的關(guān)系，即如何從一個狀態(tài)推導(dǎo)出另一個狀態(tài)。
3. 確定初始狀態(tài)和邊界條件：設(shè)置問題的起始狀態(tài)和基本情況。
4. 計算順序：確定如何計算所有狀態(tài)，通常從初始狀態(tài)開始，逐步計算到最終狀態(tài)。
5. 構(gòu)造最優(yōu)解：從最終狀態(tài)開始，逆向回溯到初始狀態(tài)，構(gòu)造問題的最優(yōu)解。

動態(tài)規(guī)劃的應(yīng)用實例：

• 背包問題：給定一組物品和一個背包，確定在不超過背包容量的前提下，背包中物品的最優(yōu)組合。
• 最長公共子序列：找出兩個序列的最長公共子序列。
• 最短路徑問題：在加權(quán)圖中找到從起點到終點的最短路徑。
• 矩陣鏈乘問題：計算矩陣序列的最優(yōu)乘法順序，以最小化總的標量乘法次數(shù)。

動態(tài)規(guī)劃是一種強大的算法設(shè)計技術(shù)，適用于解決多種復(fù)雜問題，但需要仔細分析問題的結(jié)構(gòu)，以確定是否可以應(yīng)用動態(tài)規(guī)劃方法。

題解

1. 解題思路：

1. 理解問題 給定一個正整數(shù) n，目標是找到和為 n 的完全平方數(shù)的最少數(shù)量。完全平方數(shù)是指可以表示為某個整數(shù)的平方的數(shù)，例如 1, 4, 9, 16 等。

2. 動態(tài)規(guī)劃方法 這個問題可以通過動態(tài)規(guī)劃（DP）來解決。我們定義一個數(shù)組 dp，其中 dp[i] 表示數(shù)字 i 可以由完全平方數(shù)相加得到的最少數(shù)量。

3. 初始化 DP 數(shù)組 dp[0] 初始化為 0，因為和為 0 的最少數(shù)量是 0（不需要任何數(shù)）。 對于所有其他的 i，初始化 dp[i] 為一個非常大的數(shù)（例如 INT_MAX），表示暫時無法由完全平方數(shù)相加得到。

4. 填充 DP 數(shù)組 對于每個 i 從 1 到 n，我們遍歷所有可能的完全平方數(shù) j * j（其中 j * j <= i），并更新 dp[i] 為 min(dp[i], dp[i - j*j] + 1)。這表示我們嘗試用盡可能少的完全平方數(shù)來達到數(shù)字 i。

5. 處理邊界情況 確保處理所有可能的完全平方數(shù)，包括 1（因為 1 是最小的完全平方數(shù)，且經(jīng)常出現(xiàn)在最優(yōu)解中）。 考慮所有小于或等于 i 的完全平方數(shù)。

6. 返回結(jié)果 最終，dp[n] 將包含和為 n 的完全平方數(shù)的最少數(shù)量

2. c++ demo：

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>// 動態(tài)規(guī)劃求解和為n的完全平方數(shù)的最少數(shù)量
int numSquares(int n) {std::vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= n; ++i) {int sqrt_val = static_cast<int>(std::sqrt(i));for (int j = 1; j <= sqrt_val; ++j) {dp[i] = std::min(dp[i], dp[i - j * j] + 1);}}return dp[n];
}// 主函數(shù)，用于測試
int main() {int n = 12; // 可以修改這個值來測試不同的輸入std::cout << "The least number of perfect square numbers which sum to " << n << " is: " << numSquares(n) << std::endl;return 0;
}

• 輸出結(jié)果：

The least number of perfect square numbers which sum to 12 is: 3

3. 代碼倉庫：numSquares