题目链接 ：H-数学_2023 中国大学生程序设计竞赛（CCPC）新疆赛区 (nowcoder.com)
题意 ：
有数学知识可知：
本题如果根据贪心， 每个先用最大的数来凑，会出错，比如12 == 9 + 1 + 1 + 1， 但是答案是12 == 4 + 4 + 4，就会出错
题解思路dp[], dp[i]表示从j < i 凑到i需要的最小个数,转移方程 ：dp[j] = min(dp[j], dp[j - w] + 1), 此处w时小于j的最大平方数
dp的起点时0，因此需要初始化dp[0] = 0
#include<bits/stdc++.h> using namespace std; using ull = unsigned long long; using ll = long long; using PII = pair<int,int>; #define IOS ios::sync_with_stdio(false),cin.tie(0) #define endl "\n" #define pb push_back const int N=1e5+10; const int INF=0x3f3f3f3f; const ll mod=998244353; ll f[N], dp[N]; void dfs(int st, int u, int cn) { //cout << st << ' ' << u - (int)sqrt(u) * (int)sqrt(u) << ' ' << cn + 1<< endl; if(u - (int)sqrt(u) * (int)sqrt(u) == 0) { f[st] = cn + 1; return ; } dfs(st, u - ((int)sqrt(u) * (int)sqrt(u)), cn + 1); } int main() { int n; cin >> n; memset(dp, 0x3f, sizeof dp); dp[0] = 0; ll res = 1; for(int i = 1; i * i <= n; i ++) { int w = i * i; for(int j = w; j <= n; j ++) { dp[j] = min(dp[j], dp[j - w] + 1); // if(j == 12) // { // cout <<i << ' '<< w << ' ' << j << ' ' << dp[j - w] + 1<< endl; // } } } //for(int i = 1; i <= 27; i ++) cout << f[i] << ' ';cout << endl; for(int i = 1; i <= n; i ++) res = (res * dp[i]) % mod; cout << res << endl; return 0; }