题解：P11246 [GESP202409 六级] 小杨和整数拆分

· · 题解

前言

本篇题解的解题方法为：记忆化搜索。

为什么会没有人写，明明很简单呀。

题目大意

题目十分的简短，没有什么弯弯绕绕的地方。

:::info[题目] 小杨有一个正整数 n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。

编程计算总和为 n 的完全平方数的最小数量。 :::

解题思路

这不是一道搜索吗？

我们定义一个搜索函数，dfs(int x) 它返回 x 这个数字的最小拆分数量。

退出条件：如果 x 是完全平方数，那它的最小拆分的数量一定为 1。

否则：循环 1 到 x 找到最小的dfs(x-i*i)，即 res，并返回 res+1。

:::info[Code]

#include <bits/stdc++.h>
using namespace std;

int dfs(int x){
    if(sqrt(x)==int(sqrt(x))) return 1;
    int res=INT_MAX;
    for(int i=1;i*i<=x;i++) res=min(res,dfs(x-i*i)+1);
    return res;
}

int main(){
    int n;
    cin>>n;
    cout<<dfs(n);
    return 0;
}

:::

注意到数据范围，

对全部的测试数据，保证 1 \leq n \leq 10^5。

交上去肯定 TLE，这时候我们就可以想到记忆化搜索。

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

来自 OI-Wiki - https://oi-wiki.org/dp/memo/

开一个 10^5 的数组不会 MLE，可以放心使用。

代码实现

于是，我们写出了以下代码。

主要实现方法在注释里。

#include <bits/stdc++.h>
using namespace std;

int f[100005]={};//记录已经计算过的答案，防止重复计算。

int dfs(int x){
    if(sqrt(x)==int(sqrt(x))) return 1;//如果是完全平方数，返回1
    if(f[x]) return f[x];//如果之前计算过答案，不需要重复计算，直接调用之前计算过的答案
    int res=INT_MAX;
    for(int i=1;i*i<=x;i++) res=min(res,dfs(x-i*i)+1);
    f[x]=res;//记录计算的答案，方便下次调用
    return res;
}
int main(){
    int n;
    cin>>n;
    cout<<dfs(n);
    return 0;
}

然后提交，AC 了。

AC 代码

#include <bits/stdc++.h>
using namespace std;

int f[100005]={};

int dfs(int x){
    if(sqrt(x)==int(sqrt(x))) return 1;
    if(f[x]) return f[x];
    int res=INT_MAX;
    for(int i=1;i*i<=x;i++) res=min(res,dfs(x-i*i)+1);
    f[x]=res;
    return res;
}
int main(){
    int n;
    cin>>n;
    cout<<dfs(n);
    return 0;
}

record

后记

这是本蒟蒻的第 3 篇题解，求过。

给个赞再走呗！

Update