[编程题] 一个recursion的问题
要用recursion做，不能出现loop大意是这样一个数组a1 = 10 50 40 20 50 40 30统计另一个数组a2是否包含在a1中，a2在a1中可以不连续比如另一个数组a2 =10 20 40 则只有一种包含方式， 返回1a2=50 40 30 则有3种包含方式 返回3header是int countIncludes(const double a1[], int n1, const double a2[], int n2)我的想法是算出a2中每个数在a1中出现的次数c，然后c1*c2*c3...就能得出结果，可是由于a2的样子也不清楚，我就迷茫了...求各位帮忙... 典型的DP問題，我把參數改成了int，思路是是一樣的。floatingpoint是不能用等號來比較是否相等的，有numericalprecision 的問題。int countIncludes( int a[], int n, int b[], intm){ if(m==0) return 1;// 或者 if(m<=0)，防止非法長度 if(n==0) return 0;// 或者 if(n<=0) //也可以加上if(m>n) return 0; 不加的話用下面的recursion也能得到正確答案 if(a==b ) returncountIncludes(a+1,n-1,b+1,m-1)+countIncludes(a+1,n-1,b,m); else returncountIncludes(a+1,n-1,b,m);}Time: O(nm)
页:
[1]