翡翠手镯# Fashion - 美丽时尚
I*T
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在这个问
题上毫无优势? 谢谢
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在这个问
题上毫无优势? 谢谢