一个recursion的问题

典型的DP問題，我把參數改成了int，思路是是一樣的。floating point是不能用 等號來比較是否相等的，有numerical precision 的問題。

int countIncludes( int a[], int n, int b[], int m)
{
     if(m==0) return 1; //   或者 if(m<=0)，防止非法長度
     if(n==0) return 0; //   或者 if(n<=0)  
     //也可以加上 if(m>n) return 0; 不加的話用下面的recursion也能得到正確答案

    if(a[0]==b[0] )
          return countIncludes(a+1,n-1,b+1,m-1)+countIncludes(a+1,n-1,b,m);
     else
          return countIncludes(a+1,n-1,b,m);
}

Time: O(nm)


回覆下面的同學的問題： a+1同 &a[1], 是以a+1為首地址的數組

目测LZ在上CS32……这道题我去了Smallburg的office hour听他讲了5分钟就搞定了（之前自己想了2小时+……）

edussx 发表于 2013-2-13 10:21
目测LZ在上CS32……这道题我去了Smallburg的office hour听他讲了5分钟就搞定了（之前自己想了2小时+……）

你們是在同一個學校嗎？

1L其实还少一个n1和n2的判断

1. if (n2 > n1) return 0;

复制代码

brilight 发表于 2013-2-13 10:22
你們是在同一個學校嗎？

UCLA, 这道题听说是CS32的经典题目了……

edussx 发表于 2013-2-13 10:24
1L其实还少一个n1和n2的判断

不加的話用recursion能得到正確答案，就是速度慢一點

jy02677290 发表于 2013-2-13 13:07
我想了好久都没想出来...我感觉后面的作业自己做可能有点吃力了...以后可以一起讨论啊~

Project3会很难，要做好心理准备

我QQ号私信你了