数的划分

数的划分(动态规划基础)

题目描述：一个正整数可以划分为多个正整数的和，比如n=3时： 3；1＋2；1＋1＋1； 共有三种划分方法。 给出一个正整数，问有多少种划分方法。

数据规模和约定 n< =100

输入

一个正整数n

输出

一个正整数，表示划分方案数

样例输入

 3

样例输出

 3

code:

 #include<cstdio>
 #include<iostream>
 using namespace std;
 ​
 const int N = 110;
 int f[N][N];
 //f(i,j)表示当前划分和为i，以数字j作为序列的结尾。
 int n;
 int res;
 int main(){
     scanf("%d",&n);
     f[0][0] = 1;
     
     for(int i=1;i<=n;i++){//当前和 
         for(int j=1;j<=n;j++){//以什么数结尾 
             
             //dp
             for(int k=0;k<=j;k++){//前一个数是什么 
                 //此判断切不可少！！！
                 //当前和减去当前结尾数就是前缀和，如若前缀和比直接前驱还小，那就不必要算了，方案不存在。
                 if(i-j<k)continue;
                 f[i][j] += f[i-j][k];
             }
         }
     }
     for(int i=1;i<=n;i++){
         res += f[n][i];
     }
     
     cout<<res<<endl;
     
     return 0;
 }