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

題目

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

完全平方數(shù) 是一個(gè)整數(shù)，其值等于另一個(gè)整數(shù)的平方；換句話說(shuō)，其值等于一個(gè)整數(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⁴

動(dòng)態(tài)規(guī)劃

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

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

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

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

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

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

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

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

題解

1. 解題思路：

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

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

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

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

5. 處理邊界情況 確保處理所有可能的完全平方數(shù)，包括 1（因?yàn)?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>// 動(dòng)態(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ù)，用于測(cè)試
int main() {int n = 12; // 可以修改這個(gè)值來(lái)測(cè)試不同的輸入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. 代碼倉(cāng)庫(kù)：numSquares