欢迎光临
我们一直在努力

题解:AcWing 279 自然数拆分

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来,并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构,旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏:算法题解:C++与Python实现!

附上汇总贴:算法竞赛备考冲刺必刷题(C++) | 汇总


【题目来源】

AcWing:279. 自然数拆分 – AcWing题库

【题目描述】

给定一个自然数

N

N

N,要求把

N

N

N 拆分成若干个正整数相加的形式,参与加法运算的数可以重复。

注意:

  • 拆分方案不考虑顺序;
  • 至少拆分成

    2

    2

    2 个数的和。

求拆分的方案数

m

o

d

 

2147483648

mod\\ 2147483648

mod 2147483648 的结果。

【输入】

一个自然数

N

N

N。

【输出】

输入一个整数,表示结果。

【输入样例】

7

【输出样例】

14

【算法标签】

#完全背包

【代码详解】

// 朴素做法(MLE)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4005, mod = 2147483648; // N: 最大n值,mod: 取模数
int n, f[N][N]; // n: 目标和,f[i][j]: 用前i个正整数组合出j的方案数

signed main()
{
cin >> n; // 输入目标和n

// 初始化:用任何数组合出0都只有1种方案(不选任何数)
for (int i = 0; i <= n; i++)
f[i][0] = 1;

// 动态规划:i表示当前使用的最大数,j表示目标和
for (int i = 1; i < n; i++) // 注意这里i<n,实际上使用1到n-1的数
for (int j = 0; j <= n; j++) // 遍历所有可能的目标和
{
f[i][j] = f[i – 1][j]; // 不使用数字i的情况
if (j >= i) // 如果j>=i,可以使用数字i
f[i][j] = (f[i][j] + f[i][j – i]) % mod; // 使用数字i的情况
}
cout << f[n – 1][n] << endl; // 输出用1到n-1组合出n的方案数
return 0;
}

// 降维(AC)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4005, mod = 2147483648; // N: 最大n值,mod: 取模数
int n, f[N]; // n: 目标和,f[j]: 组合出j的方案数

signed main()
{
cin >> n; // 输入目标和n

// 初始化:组合出0只有1种方案(不选任何数)
f[0] = 1;

// 动态规划
for (int i = 1; i < n; i++) // 遍历使用的数字1到n-1
for (int j = i; j <= n; j++) // 遍历目标和,从i开始
f[j] = (f[j] + f[j – i]) % mod; // 完全背包的优化,使用数字i

cout << f[n] << endl; // 输出用1到n-1组合出n的方案数
return 0;
}

【运行结果】

7
14

赞(0)
未经允许不得转载:171主机测评 » 题解:AcWing 279 自然数拆分
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址