c++题解 | #最少的完全平方数#

动态规划：

dp[i]表示正整数i最少能由多少个完全平方数组成，答案dp[n]

初始化dp[N]=INT_MAX，dp[0]=0

转移方程：dp[i+j*j] = min(dp[i+j*j] , dp[i]+1)

数字x最少组成个数来自自己本身，或者数i，并且i满足：x=i+j*j

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
const int N = 10010;
int dp[N];  // dp[i]表示正整数i最少能由多少个完全平方数组成，答案dp[n]
int numSquares2(int n) {
    //初始化dp数组
    for(int i = 0;i<N;i++){
        dp[i] = INT_MAX;
    }
    dp[0] = 0; // 0由0个完全平方数组成
    for(int i = 0; i <=n; i++){
        for(int j =1; i+j*j <=n; j++){
            // 相比于  dp[i]，dp[i+j*j] 表示i+j*j这个数由i+j*j组成，那正整数i+j*j最少能由多少个完全平方数组成取决于dp[i]+1是否小于原来的个数
            dp[i+j*j] = min(dp[i+j*j], dp[i]+1);
        }
    }
    return dp[n];
}

int main() {
    int n;
    scanf("%d", &n);
    cout << numSquares2(n) << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")