資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究用 C++ 編寫一個程式來計算完美平方數相加得到一個數
假設我們有一個正數 n，那麼我們必須找到完美平方數之和與 n 相同的最少數量。所以如果這個數是 10，那麼輸出是 2，因為這些數字為 10 = 9 + 1。
為了解決這個問題，我們將遵循以下步驟 -
- 建立一個長度為 n + 1 的動態規劃表格，並用無窮大填充
- dp[0] := 0
- 當 i := 1，且 i*i <= n 時
- x = i * i
- 當 j := x 到 n 時
- dp[j] := dp[j] 和 1 + dp[j – x] 的最小值
- 返回 dp[n]
讓我們看看以下實現，以便更好地理解 -
示例
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
public:
int solve(int n) {
vector < int > dp(n+1,INF);
dp[0] = 0;
for(int i =1;i*i<=n;i++){
int x = i*i;
for(int j = x;j<=n;j++){
dp[j] = min(dp[j],1+dp[j-x]);
}
}
return dp[n];
}
};
main(){
Solution ob;
cout << ob.solve(10);
}輸入
10
輸出
2
更新於： 2020 年 10 月 20 日
78 次瀏覽
廣告