问题描述：
大于1的正整数n可以分解为n=x1 * x2 * ... * xn
例如n=12时
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3

1<=n<=2000000000

对于这道题，我可以用递归做，不过参考书上说这题可以用动态规划做
在此请教一下大牛

你用递归都能，在上面改一下，加个备忘录储存重叠问题就是一个dp解

要用迭代也可以，思想一样的

问题描述：
大于1的正整数n可以分解为n=x1 * x2 * ... * xn
例如n=12时
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3

1<=n<=2000000000

对于这道题，请问下用递归做的程序是什么啊？

这种题用动规意义似乎不大，因为要输出具体的分解方法，不是统计有多少种分法，所以还是用递归比较好

ls不要妄下结论
对于此数据规模,必须使用DP,递归是一种算法实现方式,动态规划是一种算法思想
对于此问题,我们可以进行记忆化搜索(DP的一种实现方式),这种方法只要加一个记录状态的数组就可以了,同时也可以进行递推(顺推实现DP),后者速度更快,前者速度已可以在最大数据规模下瞬时完成计算.

/*
E-mail: sunkai [at] msn [dot] com
问题描述：
大于1的正整数n可以分解为n=x1 * x2 * ... * xn
例如n=12时
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3
1<=n<=2000000000
*/
/*
分析：
DP之记忆化搜索
状态若用d[2000000000]则内存不足
因此采用结构体记录状态
经过简单数学推理，对于一个数N,它的因子数不超过N^(1/2)+1 
*/ 
#include<stdio.h>
#include<math.h>
struct DP
{
    int num;
    int sum;
} d[50000]={0};
int max=0;
void qsort(int low,int high,struct DP key[])
{
     int i=low,j=high;
     struct DP tag=key[i];
     if(i<j)
     {
            do
            {
              while(tag.num<key[j].num && i<j) j--;
              if(i<j)
              {
                key[i]=key[j];
                i++;
                while(tag.num>=key[i].num && i<j) i++;
                if(i<j)
                {
                  key[j]=key[i];
                  j--;
                }
              }
            }while(i<j);
            key[i]=tag;
            qsort(low,j-1,key);
            qsort(i+1,high,key);
     }
}
int dfs(int left)
{
    int i,p;
    int l,r,m;
    int count=0;
    l=0; r=max;
    while(l<=r)
    {
      m=(l+r)>>1;
      if(d[m].num<left) l=m+1; else r=m-1;
    }
    p=l; if(d[p].sum) return d[p].sum;
    for(i=1;i<=d[i].num;i++)
    {
      if(left%d[i].num==0) count+=dfs(left/d[i].num);
    }
    d[p].sum=count;
    return count;
}
int main(void)
{
    int i,j,tmp;
    int n;
    scanf("%d",&n); tmp=sqrt(n);
    for(i=1;i<=tmp;i++)
    {
      if(n%i==0)
      {
        d[max].num=i; max++;
        d[max].num=n/i; max++;
      }
    } max--;
    qsort(0,max,d);
    d[0].sum=1;
    printf("%d\n",dfs(n));
    return 0;
}

[[it] 本帖最后由 卧龙孔明 于 2008-3-21 20:26 编辑 [/it]]

以上程序经过优化,时间复杂度为
W(n^(1.5)logn)+W(n^0.5log(n^0.5))+W(n^0.5)
即为
O(n^(1.5)logn)
空间复杂度为
O(n^0.5)
已经可以瞬间出解
再次重申,如果单纯是递归,甚至是单纯DP,对于本程序的最大数据所需计算时间是巨大的,前者是无法估计的.

改过的代码直接在上，等从新题区移走后就可以看到了，算法思想已经给出，同时ac的代码就是在上面的代码上改几句就可以了