I********T
发帖数: 22 | 1 题目是leetcode上online judge的combination， 就是n个数(1,2,3,4...n)找k个数的
combination. 一般都用递归做，可是这样就会把有些combination重复算。 比如： C(
n,k) = C(n-1, k-1) + C(n-1, k) = C(n-2, k-2) + C(n-2,k-1) + C(n-2,k-1) + C(n
-2, k). 这样C(n-2,k-1)就重复了。 如果用dp做的话就可以缓存C(n-2,k-1)的结果。
这两种复杂度各是多少呢? 我觉得递归做是C(n,k)，因为复杂度公式和combination计
算公式一样。 dp做好像是N*k （假设我们用table缓存结果）。 可是由于table里每个
格子的存的元素数目大于一，所以复杂度还是C(n,k)。
这样的话是不是说dp在这个问
题上毫无优势? 谢谢 | i*********7
发帖数: 348 | |
|
