---
title: "自然数拆分"
created: 2025-11-28
tags:
  - 算法
---

# 自然数拆分

## 题目 [自然数拆分](https://www.acwing.com/problem/content/description/281/)

![[image-2059c8aa.png]]

## 思路分析

可以理解成背包问题

怎么转变成呢

先举个例子 3可以拆分成 1 2吧 不能拆成0 3 因为最少要拆分成两个数个和 也就是说 在前3-1个物品里选 价值不超过3的选法的数量 变量变成了一个

用dp分析法来看

（直接画优化后的图了 优化后其实就是一个反过来的01背包 所以也就是选与不选两种）

![[image-2fe0ed33.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=4010;

long long mod=2147483648;

long long dp[N];

int n;

int main()

{

    cin>>n;

    dp[0]=1;//什么都不选也是一种选法

    for(int i=1;i<n;i++){

        for(int j=i;j<=n;j++){//完全背包 从小到大

            dp[j]=(dp[j]+dp[j-i])%mod;

        }

    }

    cout<<dp[n];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[整数拆分|整数拆分]] 🏠 [[00-刷题理模型]] ➡️ [[货币系统|货币系统]]