[蓝桥杯 2016 省 AB] 四平方和
题目描述
四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：5=0^2+0^2+1^2+2^2。7=1^2+1^2+1^2+2^2。
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序使得 0≤a≤b≤c≤d。
并对所有的可能表示法按a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式
程序输入为一个正整数 N(N<5×10^6)。
输出格式
要求输出 4个非负整数，按从小到大排序，中间用空格分开。
代码表示
#include<bits/stdc++.h>
using namespace std;
int n;
int check(int a,int b,int c,int d){return a*a+b*b+c*c+d*d;}
//求a^2+b^2+c^2+d^2
int main()
{
cin>>n;
for(int i=0;;i++)
{
if(check(i,i,i,i)>n) break;//边界判断
for(int j=i;;j++)
{
if(check(i,j,j,j)>n) break;
for(int k=j;;k++)
{
if(check(i,j,k,k)>n) break;
else
{
int s=sqrt(n-check(i,j,k,0));
if(check(i,j,k,s)==n)
return cout<<i<<" "<<j<<" "<<k<<" "<<s,0;
}
}
}
}
}心得体会
对于return cout<<i<<” “<<j<<” “<<k<<” “<<s，0； 在这个语句中，s, 0 表示逗号操作符。逗号操作符用于将多个表达式组合在一起，并按顺序依次执行这些表达式。这样做是为了在输出符合条件的组合后立即结束程序。
[蓝桥杯 2021 省 AB2] 完全平方数
题目描述
一个整数a 是一个完全平方数，是指它是某一个整数的平方，即存在一个 整数b，使得 a=b^2 。
给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n。
输出格式
输出找到的最小的正整数 x
代码表示
第一：我的代码，只有30分，由于超时了/(ㄒoㄒ)/~~
#include<bits/stdc++.h>
using namespace std;
long long n,num=0;
long long cj(long long n){
for(int i=1;i<=n;++i){
num=n*i;
for(int j=1;j<=num/2;++j){
if(j*j==num){
return i;
}
}
}
return -1;
}
int main()
{
cin>>n;
cout<<cj(n);
return 0;
}
第二
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n,x=1;
scanf("%lld",&n);
for(long long i=2;i*i<=n;i++)//扫描质因数i
if(n%i==0)
{
int cnt=0;
while(n%i==0)//去除这个质因数，计数
{
n/=i;
cnt++;
}
if(cnt%2==1) x*=i;
}
if(n!=1) x*=n;//n为质数
printf("%lld\n",x);
return 0;
}心得体会
1、注意在写程序的函数的时候，一定要注意有返回值比如上面我自己写的那个超时程序，开始就没有写return -1导致代码无法正常输出。
2、我们发现，一个完全平方数分解质因数后，每个质因数的指数一定是偶数，因为完全平方数是通过两个相同的整数相乘得到的。因此做法如下：
得到 n 后，先将 x 初始化为 1。随后再扫描 n 的所有质因数，将 n 除掉所有这个质因数。判断这个质因数的指数：如果为奇数就将 x 乘上这个质因数与 n 配对成偶数。最后，如果最后 n≠0，说明 n 为质数，我们就没有判断它，x←x×n。
3、假设输入 n 是 20。代码：
1）首先从 i=2 开始，发现 n 可以整除 2，所以质因数为 2；
2）通过内部循环计算 n 中有 2 的个数，并将 n 除以 2。
3）接着，继续扫描，发现 n 可以整除 5，所以质因数为 5；
4）通过内部循环计算 n 中有 5 的个数，并将 n 除以 5。
5）此时，n 变为 1。最后，判断 n 不等于 1，说明 n 是一个质数，将其乘到 x 上。
6）所以最终得到的 x 为 2 * 5 * 1 = 10。
[蓝桥杯 2019 省 AB] 完全二叉树的权值
题目描述
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋯AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 11。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋯,AN。
输出格式
输出一个整数代表答案
代码表示
#include<bits/stdc++.h>
using namespace std;
#define int long long
//maxx 的目的是用于记录权值之和的最大值其初始化为一个较小的值以确保在比较中能够正确更新为更大的值。
int maxx=-1e18,maxid;
int n;
int now,k=1;//这一层输入了几个数了；是第几层了
int ans;//存每一层的权值和
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
ans+=x;
now++;//记录已经输入几个节点
//表示已经输入了当前层的最后一个节点或者已经输入完所有节点。
if(now==pow(2,k-1)||i==n)
{
// maxx 来记录当前找到的权值之和最大的深度的权值和
if(ans>maxx)
{
maxx=ans;
maxid=k;//最小的深度
}//更大
ans=now=0;//重置
k++;//下一层
}
}
return cout<<maxid,0;
}心得体会
二叉树是一种常见的树状数据结构，它由节点（Node）组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。
以下是一些关于二叉树的重要概念和术语：
-
节点（Node）：二叉树的基本单位，包含一个数据元素以及指向左子节点和右子节点的指针。
-
根节点（Root）：二叉树的顶部节点，没有父节点。
-
叶节点（Leaf）：没有子节点的节点，也称为终端节点。
-
内部节点（Internal Node）：除了叶节点以外的所有节点，即有至少一个子节点的节点。
-
子树（Subtree）：二叉树中的任意节点及其所有后代节点构成的子树。
-
左子树和右子树：一个节点的左子树是以该节点的左子节点为根的子树，右子树是以该节点的右子节点为根的子树。
-
深度（Depth）：节点所在的层数，根节点的深度为 0，其子节点的深度为 1，依此类推。
-
高度（Height）：树的高度等于根节点到最远叶节点的最长路径的深度。
-
完全二叉树（Complete Binary Tree）：除了最后一层外，其他层的节点都是满的，最后一层的节点都靠左排列。
-
满二叉树（Full Binary Tree）：每个节点要么没有子节点，要么有两个子节点。
-
二叉查找树（Binary Search Tree）：一种特殊的二叉树，对于每个节点，其左子树上的所有节点的值都小于节点的值，而右子树上的所有节点的值都大于节点的值。
完全背包理论
1、有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
2、完全背包和01背包问题唯一不同的地方就是：每种物品有无限件。
背包最大重量为4，物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！
因为dp[j] 是根据下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。但这是对于纯完全背包问题，其for循环的先后循环是可以颠倒的！但如果题目稍稍有点变化，就会体现在遍历顺序上。
完整的C++测试代码如下：
// 先遍历物品，在遍历背包
void test_CompletePack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_CompletePack();
}
// 先遍历背包，再遍历物品
void test_CompletePack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_CompletePack();
}
携带研究材料
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择（完全背包）。
输入描述
第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间
接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
输出描述
输出一个整数，表示最大价值。
输入示例
4 5
1 2
2 4
3 4
4 5输出示例
10提示信息 第一种材料选择五次，可以达到最大值。
数据范围：
1 <= N <= 10000；1 <= V <= 10000；1 <= wi, vi <= 10^9.
代码表示
#include<bits/stdc++.h>
using namespace std;
// 先遍历背包，再遍历物品
void test_CompletePack(vector<int>weight, vector<int>value, int bagWeight) {
vector<int> dp(bagWeight + 1, 0);
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
int N, V;
cin>>N>>V;
vector<int> weight;
vector<int> value;
for (int i = 0; i < N; i++) {
int w;
int v;
cin >> w >> v;
weight.push_back(w);
value.push_back(v);
}
test_CompletePack(weight, value, V);
return 0;
}零钱兑换Ⅱ
题目描述
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
思路提示
1、类似于之前目标和的问题。不强调顺序，先遍历物品后背包是组合数
2、纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数。
例如示例一：
5 = 2 + 2 + 1；5 = 2 + 1 + 2
这是一种组合，都是 2 2 1；但如果是排列的话就是两种。
动规五步曲来分析如下：
1、确定dp数组以及下标的含义：dp[j]：凑成总金额j的货币组合数为dp[j]
2、确定递推公式：dp[j] 就是所有的dp[j – coins[i]]（考虑coins[i]的情况）相加。
所以递推公式：dp[j] += dp[j – coins[i]]；这个递推公式就是求装满背包有几种方法。
3、dp数组如何初始化：
首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。
但题目描述中没明确说 amount = 0 的情况，结果应该是多少。下标非0的dp[j]初始化为0，这样累计加dp[j – coins[i]]的时候才不会影响真正的dp[j]
dp[0]=1还说明了一种情况：如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选法。
4、确定遍历顺序
纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系。本题是求凑出来的方案个数，且每个方案个数是为组合数。两个for循环的先后顺序可就有说法了。
先来看外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。
代码如下：（这个遍历开头的背包是从coins[i]开始的)
for (int i = 0; i < coins.size(); i++) { // 先遍历物品
for (int j = coins[i]; j <= amount; j++) { // 后遍历背包容量
dp[j] += dp[j - coins[i]];
}
}
假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < coins.size(); i++) { // 遍历物品
if (j - coins[i] >= 0)
dp[j] += dp[j - coins[i]];
}
}
背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
5、举例推导dp数组
输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：
代码表示
#include<bits/stdc++.h>
using namespace std;
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
int main() {
int amount;
cin >> amount;
int numCoins;
cin >> numCoins;
vector<int> coins(numCoins);
for (int i = 0; i < numCoins; ++i) {
cin >> coins[i];
}
cout <<change(amount, coins)<< endl;
return 0;
}组合总数Ⅱ
题目描述
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums中的所有元素 互不相同1 <= target <= 1000
思路提示
先背包后物体是排列数，他是强调元素顺序的。
动规五部曲分析如下：
1、确定dp数组以及下标的含义 dp[i]: 凑成目标正整数为i的排列个数为dp[i]
2、确定递推公式
dp[i]（考虑nums[j]）可以由 dp[i – nums[j]]（不考虑nums[j]） 推导出来。
因为只要得到nums[j]，排列个数dp[i – nums[j]]，就是dp[i]的一部分。
在目标和和零钱兑换中已经讲过了，求装满背包递推公式一般都是dp[i] += dp[i – nums[j]];
3、dp数组如何初始化
因为递推公式dp[i] += dp[i – nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
4、确定遍历顺序
个数可以不限使用，说明这是一个完全背包。
得到的集合是排列，说明需要考虑元素之间的顺序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
5、举例来推导dp数组 我们再来用示例中的例子推导一下：
代码表示
#include<bits/stdc++.h>
using namespace std;
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) { // 遍历背包
for (int j = 0; j < nums.size(); j++) { // 遍历物品
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]])
{
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
int main() {
int n;
cin>>n;
vector<int>nums(n);
for (int i=0;i<n;++i) {
cin >> nums[i];
}
int target;
cin >>target;
cout <<combinationSum4(nums,target)<<endl;
return 0;
}爬楼梯进阶版
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述 输入共一行，包含两个正整数，分别表示n, m
输出描述 输出一个整数，表示爬到楼顶的方法数。
输入示例
3 2输出示例
3提示信息
数据范围：1 <= m < n <= 32;
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。此时你有三种方法可以爬到楼顶。
1）1 阶 + 1 阶 + 1 阶段；2）1 阶 + 2 阶；3）2 阶 + 1 阶
思路提示：
这又有难度了，这其实是一个完全背包问题。1阶，2阶，…. m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。问跳到楼顶有几种方法其实就是问装满背包有几种方法。类似于组合总和问题
动规五部曲分析如下：
1、确定dp数组以及下标的含义： dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
2、确定递推公式：同目标和和零钱兑换和组合总和，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i – nums[j]];
本题dp[i]有几种来源，dp[i – 1]，dp[i – 2]，dp[i – 3] 等等，即：dp[i – j]
那么递推公式为：dp[i] += dp[i – j]
3、dp数组如何初始化
递归公式是 dp[i] += dp[i – j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果
4、确定遍历顺序
这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！
所以需将target放在外循环，将nums放在内循环。每一步可以走多次，这是完全背包，内循环需要从前向后遍历。
代码表示：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) { // 遍历背包
for (int j = 1; j <= m; j++) { // 遍历物品
if (i - j >= 0) dp[i] += dp[i - j];
}
}
cout << dp[n] << endl;
}
}零钱兑换Ⅰ
题目描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
提示：
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
思路提示
动规五部曲分析如下：
1、确定dp数组以及下标的含义 dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
2、确定递推公式
凑足总额为j – coins[i]的最少个数为dp[j – coins[i]]，那么只需要加上一个钱币coins[i]即dp[j – coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j – coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j – coins[i]] + 1, dp[j])；注意滚动数组
3、dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j – coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。
代码如下：
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
4、确定遍历顺序
本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！
那么我采用coins放在外循环，target在内循环的方式。本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序
故遍历顺序为：coins（物品）放在外循环，target（背包）在内循环。且内循环正序。
5、举例推导dp数组
以输入：coins = [1, 2, 5], amount = 5为例
代码表示
#include<bits/stdc++.h>
using namespace std;
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
}
}
}
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
int main() {
int n;
cin>>n;
vector<int>coins(n);
for (int i=0;i<n;++i) {
cin >>coins[i];
}
int amount;
cin >>amount;
cout <<coinChange(coins,amount)<<endl;
return 0;
}完全平方数
题目描述
给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
思路提示
完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？和上一道一样；
动规五部曲分析如下：
1、确定dp数组（dp table）以及下标的含义 dp[j]：和为j的完全平方数的最少数量为dp[j]
2、确定递推公式
dp[j] 可以由dp[j – i * i]推出， dp[j – i * i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j – i * i] + 1, dp[j]);
3、dp数组如何初始化
dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。
看题目描述，找到若干个完全平方数（比如 1, 4, 9, 16, …），题目描述中可没说要从0开始，dp[0]=0完全是为了递推公式。
非0下标的dp[j]应该是从递归公式dp[j] = min(dp[j – i * i] + 1, dp[j])；中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
4、确定遍历顺序
本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！
先给出外层遍历背包，内层遍历物品的代码：
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; i++) { // 遍历背包
for (int j = 1; j * j <= i; j++) { // 遍历物品
dp[i] = min(dp[i - j * j] + 1, dp[i]);
}
}
5、举例推导dp数组
已输入n为5例，dp状态图如下：
dp[0] = 0 dp[1] = min(dp[0] + 1) = 1 dp[2] = min(dp[1] + 1) = 2 dp[3] = min(dp[2] + 1) = 3 dp[4] = min(dp[3] + 1, dp[0] + 1) = 1 dp[5] = min(dp[4] + 1, dp[1] + 1) = 2；最后的dp[n]为最终结果。
代码表示
#include<bits/stdc++.h>
using namespace std;
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; i++) { // 遍历背包
for (int j = 1; j * j <= i; j++) { // 遍历物品
dp[i] = min(dp[i - j * j] + 1, dp[i]);
}
}
return dp[n];
}
int main() {
int n;
cin>>n;
cout <<numSquares(n)<<endl;
return 0;
}或
#include<bits/stdc++.h>
using namespace std;
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i * i <= n; i++) { // 遍历物品
for (int j = i * i; j <= n; j++) { // 遍历背包
dp[j] = min(dp[j - i * i] + 1, dp[j]);
}
}
return dp[n];
}
int main() {
int n;
cin>>n;
cout <<numSquares(n)<<endl;
return 0;
}版权声明：本文为博主作者：小杨想赢一次原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_63597914/article/details/137329221
