仅使用2或3从0到达N的方法的数量？

Question

我正在解决这个问题,我们需要从X = 0到X = N.我们一次只能采取2或3步.

对于2的每一步,我们的概率为0.2,对于每步3,我们的概率为0.8.我们如何找到达到N的总概率.

例如,达到5,

2+3 with probability =0.2 * 0.8=0.16

3+2 with probability =0.8 * 0.2=0.16 total = 0.32.

我最初的想法:

通过简单的Fibonacci序列可以找到多种方法.F(N)= F(N-3)+ F(N-2); 但是,我们如何记住这些数字,以便我们可以将它们相乘以找出概率？

Answer 1

这可以使用Dynamic programming.

让我们调用函数F(N)=概率到达时0只使用2和3the 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)