【题解】自然数拆分

题目链接

解题思路

本题 dpi 表示的是有 i 个数字和为 j,由于每个 i 都是不断更新的,不会访问之前的 i,所以可以直接滚动数组:dp[j]代表当前数字和为 j。

代码

#include<bits/stdc++.h>
using namespace std;
long long dp[10005];
const long long mod=2147483648;
int main(){
    int n;
    cin>>n;
    dp[0]=1;
    for(int i=1;i<=n;i++){//有i个数字,和为j 
        for(int j=i;j<=n;j++){
            dp[j]+=dp[j-i];
            dp[j]%=mod;
        }
    }
    cout<<dp[n]-1;
    return 0;
}