x*******t
发帖数: 3 | 1 Take a ladder with 5 steps, write a function that gives all the possible
combinations of either 1,2, or 3 steps, in any order, to get to the 5th step
, and returns the total number of combinations. So some of the possibilities
would be [1,1,1,1,1], [1,1,1,2], [1,1,2,1], etc. Then he asked the same
question with order not being considered, so [1,1,1,2] and [1,1,2,1] are the
same solution.
The first one for ladder with order is simple by recursive .
static int getLadderWithOrder(int n) {
if (n <= 0)
return 0;
if(n==1)
return 1;
if(n==2)
return 2;
if(n==3)
return 4;
return getLadderWithOrder(n-1) + getLadderWithOrder(n-2) +
getLadderWithOrder(n-3);
}
Is there better way to solve the second one for ladder without order?
Thanks | c********p
发帖数: 1969 | | f******n
发帖数: 279 | | m******e
发帖数: 82 | 4 P1:
f[i] = f[i-1] + f[i-2] + f[i-3], f[n] is the result
P2:
for 1<= i <=n
f[1][i] = 1, // last step is 1
f[2][i] = f[1][i-2] + f[2][i-2], // last step is 2
f[3][i] = f[1][i-3] + f[2][i-3] + f[3][i-3], // last step is 3
so, f[1][n] + f[2][n] + f[3][n] is the result | x******0
发帖数: 178 | 5 这个能解释一下么，
比如说
f[1][3] 可以是2，1或者1，1，1. 为什么f[1][3] = 1 呢？
【在 m******e 的大作中提到】
: P1:
: f[i] = f[i-1] + f[i-2] + f[i-3], f[n] is the result
: P2:
: for 1<= i <=n
: f[1][i] = 1, // last step is 1
: f[2][i] = f[1][i-2] + f[2][i-2], // last step is 2
: f[3][i] = f[1][i-3] + f[2][i-3] + f[3][i-3], // last step is 3
: so, f[1][n] + f[2][n] + f[3][n] is the result
| k***s
发帖数: 6 | 6 抛砖
class MyClass(object):
def __count_jumps_1(self, remaining_steps, memory):
if memory[remaining_steps] is None:
count = 0
for jump in (1, 2, 3):
if remaining_steps >= jump:
count += self.__count_jumps_1(remaining_steps - jump,
memory)
else:
break
memory[remaining_steps] = count
return memory[remaining_steps]
def count_jumps_1(self):
memory = [None] * 6
memory[0] = 1
return self.__count_jumps_1(5, memory)
def __count_jumps_2(self, remaining_steps, cap, memory):
if memory[remaining_steps][cap] is None:
count = 0
for jump in range(cap, 0, -1):
if jump <= remaining_steps:
count += self.__count_jumps_2(remaining_steps - jump,
jump, memory)
memory[remaining_steps][cap] = count
return memory[remaining_steps][cap]
def count_jumps_2(self):
memory = [[None] * 4] * 6
memory[0] = [1, 1, 1, 1]
return self.__count_jumps_2(5, 3, memory)
print MyClass().count_jumps_1() #13
print MyClass().count_jumps_2() #5 | x******0
发帖数: 178 | 7 想明白了。步骤必须是顺序的。最后一步是1，前面的步必须也是1。这个题目和找钱差
不多啊。 | x*******t
发帖数: 3 | 8 what f[1][i] represent here??
【在 m******e 的大作中提到】
: P1:
: f[i] = f[i-1] + f[i-2] + f[i-3], f[n] is the result
: P2:
: for 1<= i <=n
: f[1][i] = 1, // last step is 1
: f[2][i] = f[1][i-2] + f[2][i-2], // last step is 2
: f[3][i] = f[1][i-3] + f[2][i-3] + f[3][i-3], // last step is 3
: so, f[1][n] + f[2][n] + f[3][n] is the result
| x*******t
发帖数: 3 | 9 Not clear for the following
步骤必须是顺序的。最后一步是1，前面的步必须也是1。
Could you explain more? The last step is 1 , the previous could be 2 or 3
, why it must be 1?
Thanks | x******0
发帖数: 178 | 10 1,2,3 和3，2，1算一样的走法。所以只要考虑所有是升序的走法。
如果最后一步是1，那前面的肯定也只有1了。
3
【在 x*******t 的大作中提到】
: Not clear for the following
: 步骤必须是顺序的。最后一步是1，前面的步必须也是1。
: Could you explain more? The last step is 1 , the previous could be 2 or 3
: , why it must be 1?
: Thanks
|
|
