f*****u
发帖数: 308 | 1 下面这段代码是Leetcode上面Unique Paths的最基本的recursion算法。它的算法复杂
度咋算？哪个高手给解释一下，多谢！
int uniquePaths(int m, int n) {
if (m < 1 || n < 1) return 0;
if (m == 1 && n == 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
} |
v******F
发帖数: 61 | |
q********c
发帖数: 1774 | 3 这题用recursion就是fail的节奏啊.
【在 f*****u 的大作中提到】
: 下面这段代码是Leetcode上面Unique Paths的最基本的recursion算法。它的算法复杂
: 度咋算？哪个高手给解释一下，多谢！
: int uniquePaths(int m, int n) {
: if (m < 1 || n < 1) return 0;
: if (m == 1 && n == 1) return 1;
: return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
: }
|
s**x
发帖数: 7506 | 4
right, 楼主显然需要潜心研究 dynamic programming chapter for 2 months at
least.
【在 q********c 的大作中提到】
: 这题用recursion就是fail的节奏啊.
:
:
|
f*****u
发帖数: 308 | 5 我算的也是这样。但是这个解答里面说是4^n。看来是这个答案里面是有问题的。
【在 v******F 的大作中提到】
: 应该是2^(m+n)吧！
|
f*****u
发帖数: 308 | 6 好吧，我只是问一下这道题的这种recursion基本解法的算法复杂度的分析问题撒。当
然知道这题有dp的优化解法。不过还是感谢提醒吧。
【在 s**x 的大作中提到】
:
: right, 楼主显然需要潜心研究 dynamic programming chapter for 2 months at
: least.
|
