【题解】自然数拆分

题目链接

解题思路

做这题我还看了题解真是奇耻大辱。

本题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;
} 

本文链接:http://kaispace.com.cn/index.php/archives/762/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者