algorithm - 仅使用 2 或 3 种从 0 到达 N 的方法？

我正在解决这个问题，我们需要从 X=0 到达 X=N。我们一次只能走 2 或 3 步。

对于 2 的每一步，我们有 0.2 的概率，对于 3 的每一步，我们有 0.8 的概率。我们如何找到达到 N 的总概率。



我的初步想法:

可以通过简单的斐波那契数列找出多种方法。
f(n)=f(n-3)+f(n-2)；
但是我们如何记住这些数字以便我们可以将它们相乘以找到概率？

最佳答案

这可以使用 Dynamic programming 解决。

让我们调用函数 F(N) = 当 0 时仅使用 2 和 3 达到 the starting number is N 的概率

F(N) = 0.2*F(N-2) + 0.3*F(N-3)

基本情况:

F(0) = 1 and F(k)= 0 where k< 0

所以 DP 代码将是这样的:

F[0] = 1;
for(int i = 1;i<=N;i++){
     if(i>=3)
         F[i] = 0.2*F[i-2] + 0.8*F[i-3];
     else if(i>=2)
         F[i] = 0.2*F[i-2];
     else
         F[i] = 0;
}
return F[N];

该算法将在 O(N) 中运行

关于algorithm - 仅使用 2 或 3 种从 0 到达 N 的方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30668884/