数学_四平方定理

题目链接 ：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;
}