*joj 1026 the staircase 利用递归、动态规划跟一道类似题目

***joj 1026 the staircase 利用递归、动态规划和一道类似题目

?

转自网易何国涛的博客http://zhedahht.blog.163.com/blog/static/25411174200732711051101/

题目：输入一个正数n，输出所有和为n连续正数序列。

?

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。

?

分析：这是网易的一道面试题。

?

这道题和本面试题系列的第10题有些类似。我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2，因为序列至少要有两个数字。

?

基于这个思路，我们可以写出如下代码：

?

void PrintContinuousSequence(int small, int big);/////////////////////////////////////////////////////////////////////////// Find continuous sequence, whose sum is n/////////////////////////////////////////////////////////////////////////void FindContinuousSequence(int n){      if(n < 3)            return;      int small = 1;       int big = 2;      int middle = (1 + n) / 2;      int sum = small + big;      while(small < middle)      {            // we are lucky and find the sequence            if(sum == n)                  PrintContinuousSequence(small, big);            // if the current sum is greater than n,             // move small forward            while(sum > n)            {                  sum -= small;                  small ++;                  // we are lucky and find the sequence                  if(sum == n)                        PrintContinuousSequence(small, big);            }            // move big forward            big ++;            sum += big;      }}/////////////////////////////////////////////////////////////////////////// Print continuous sequence between small and big/////////////////////////////////////////////////////////////////////////void PrintContinuousSequence(int small, int big){      for(int i = small; i <= big; ++ i)            printf("%d ", i);      printf("\n");}

/*题意:将数字N分成2份以上.使用的数字不可重复.例如5=1+4=2+3,就只有两种拆分的方式.输入:每一行给出一个数字N,3<=N<=500.整个测试以0代表结束.方法1，动态规划这道题只要求计数，我们考虑是否能用递推、DP、组合数学的方法解决。 如果不理会题目中要求阶梯数不能为1的条件（即不能用自己组成自己），那么这道题要求的实际上就是从1,2,3,...,n这个正整数序列中选数来组成n的种类数，我们最后只要减去1（就是用自己组成自己的那一种）就行。 设f[a,b]表示用正整数序列中前b个数组成a的种类数，我们以b为阶段进行计算。添加上第b个正整数(也就是b)后，我们可以用b来组成a，也可以不用b，于是就有f[a,b]=f[a-b,b-1]+f[a,b-1]。 对于边界条件，我们考虑，很明显有f[1,1]=1，而f[1,1]=f[1-1,1-1]=f[0,0]=1，所以边界条件为f[0,0]=1。注意到第b阶段只和第b-1阶段有关，所以可以省掉b维，只需要用两个数组f0，f1滚存，f0存第b-1阶段，f1存第b阶段，就可以了，初始状态为f0[0]=1。又观察到计算f1[a]时，只与f0中比a小的状态有关，于是可以采取将a从大到小计算，这样只需要用一个数组就可以解决问题了。 这道题如果用搜索，肯定爆TLE没救。由于题目的结果比较大，得用Extended来存贮。如果用另一种二维DP，会爆MLE，用这种一维DP则不会 方法2：生成函数法(其实就是 仅使用一维状态 的dp )计算(1+x)(1+x^2)(1+x^3)-----,x^n的系数即为所求int i,j;double ans[510]={1,1};//已经把ans[1]和ans[0]赋为1了，其余为0for(i=2;i<=500;i++) {           for(j=500;j>=0;j--) //逆序{              if(i+j<=500) ans[i+j]+=ans[j];         }      }  先计算(1+x)(1+x^2)再计算(1+x)(1+x^2)   *(1+x^3)*/#include<iostream>#include<cstdlib>using namespace std;double dp[501][501]={0}; //这个为动态规划使用/* 使用二维状态的 dp*/int dpBasic(int num){dp[0][0] = 1;/*dp[0][1] = dp[1][0] = 0;for(int k=1;k<=500;k++)dp[k][1] = 1;for(int i=0;i<=500;i++) //i 从 0开始{for(int j=1;j<=i;j++) //由于 j - 1 的存在 所以 下界 1dp[i][j] = dp[i-j][j-1] + dp[i][j-1];}*/int i,k;for(i = 0; i < 501; i ++){for(k = 1; k <= i; k ++)dp[i][k] = dp[i - k][k - 1] + dp[i][k - 1];for(k = i + 1; k < 501; k ++)//k > i时候 dp[i][k] = dp[i][i],这些是必须的，因为防止后面的计算需要这些东西dp[i][k] = dp[i][i];}return dp[num][num] -1;}/*仅适用一维的动态规划  注意：转成一维的时候，注意必用一个逆循环，为什么是不是正循环*/double inta[502] ; // int 时 wrong answer，此处使用一维int dpAd(int num){int i , j;int n ;inta[0] = 1 ;for ( i =1 ;i <= 500 ;i++ )for( j =500 ;j >= i ;j -- ) //此处是逆循环inta[j] += inta[j-i] ;return inta[num] - 1;}int main(){while(scanf("%d",&n),n) { printf("%d\n",dpBasic(n)); } return   0;}