Sea*_*anT -1 algorithm permutation
我被要求建立一个涉及排列的算法,我有点难过,并寻找起点.细节是......
你正在爬楼梯的n楼梯.每次你可以一次爬1或2步.有多少种不同的方式可以爬到顶端？
我有什么建议可以应对这一挑战吗？
你对排列错了.排列涉及一组的排序.这个问题是别的.
涉及产生同一问题的另一个实例的简单决策的问题通常可通过动态编程来解决.这是一个问题.
当你有n个爬升步骤时,你可以选择1步或2步的跳跃,然后分别解决n-1和n-2步的较小问题.在这种情况下,您想要添加可能性的数量.(很多DP都要找到最小值或最大值,所以这有点不寻常.)
"基本情况"是指您有0步或1步.只有一种方法可以遍历这些方法.
考虑到所有这些,我们可以编写这个动态程序,用于爬行n步作为递归表达式的方式:
W(n) = W(n - 1) + W(n - 2) if n > 1
1 n == 0, 1
现在您不希望将其实现为简单的递归函数.计算n需要指数时间,因为每次调用W都会调用两次.然而,大多数这些电话都是不必要的重复.该怎么办？
完成工作的一种方法是找到一种按顺序计算W(i)值的方法.对于1值DP,它通常很简单,所以它在这里:
W(0) = 1
W(1) = 1 (from the base case)
W(2) = W(1) + W(0) = 1 + 1 = 2
W(3) = W(2) + W(1) = 2 + 1 = 3
你明白了.这确实是一个非常简单的DP.为了计算W(i),我们只需要两个先前的值,W(i-1)和W(i-2).一个简单的O(n)循环就可以了.
作为一个完整性检查,请看W(3)= 3.事实上,要达到3个步骤,我们可以采取1到2,2然后是1或3跳的跳跃.这是3种方式!
又忍不住了？W(4)= 2 + 3 = 5.跳跃序列是(2,2),(2,1,1),(1,2,1),(1,1,2)和(1,1,1,1):5种方式.
事实上,上面的图表看起来很熟悉.爬n步的方法数是第(n + 1)个斐波纳契数.你应该自己编写循环代码.如果卡住,您可以查找数百个已发布的示例中的任何一个.