왜 내 계산 계산에 실패 했습니까?

Question

저는 2 차원 재귀 문제를 동적 프로그래밍 문제로 바꾸려고합니다. 그러나 결과는 다릅니다. 결과가 다른 이유

import edu.princeton.cs.algs4.*; 
import java.util.Arrays; 

public class Test { 

    public static double binomial(int N, int k, double p) { 
     if(N == 0 && k == 0) return 1.0; 
     if(N < 0 || k < 0) return 0.0; 
     return (1 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1, p); 
    } 

    public static double binomialm(int N, int k, double p) { 
     if(N < 0 || k < 0) return 0.0; 

     double[][] memory = new double[N+1][k+1]; 
     memory[0][0] = 1.0; 
     memory[1][0] = 1 - p; 
     memory[0][1] = 0.0; 

     for(int i = 1; i <= N; i++) { 
      for(int j = 1; j <= k; j++) { 
       memory[i][j] = (1 - p)*memory[i-1][j] + p*memory[i-1][j-1]; 
      } 
     } 

     return memory[N][k]; 
    } 

    static public void main(String args[]) { 
     long stime, stime1, etime, etime1; 
     double r, r1; 
     stime = System.currentTimeMillis(); 
     r = binomial(10, 5, 0.25); 
     etime = System.currentTimeMillis(); 
     System.out.println("Regular binomial: result = " + r + ", time = " + (etime - stime)); 
     stime1 = System.currentTimeMillis(); 
     r1 = binomialm(10, 5, 0.25); 
     etime1 = System.currentTimeMillis(); 
     System.out.println("Memoized binomial: result = " + r1 + ", time = " + (etime1 - stime1)); 
    } 
} 

정말 알아낼 수 없습니다 : 여기

는 코드입니다. 여기에 그들이있다 :

정기적 인 이항 : 결과 = 0.058399200439453125, 시간 = 0

는 이항 Memoized : 결과 = 0.045421600341796875, 시간 = 0

내가 놓친 게 몇 가지 부동 소수점 마법이 있습니까?

Answer 1

메모 한 버전에서 내부 루프는 j = 1에서 시작됩니다. 따라서 (2,0), (3,0), (4,0), ...의 값은 절대로 변경되지 않으며, 이중 배열 생성에서 여전히 0.0입니다. 그들은 1.0, -1.0, 1.0, ...이라고 가정합니다.

for(int i = 1; i <= N; i++) { 
    memory[i][0] = (1 - p)*memory[i-1][0]; 
    for(int j = 1; j <= k; j++) { 
     memory[i][j] = (1 - p)*memory[i-1][j] + p*memory[i-1][j-1]; 
    } 
}