Memoized Rod Cutting Algorithm

Question

我正在嘗試實現memoized版本的遞歸杆切割算法。這裏是我的代碼（我實現了從Cormen的僞代碼）

public class simpleMemoized { 

    //finds maximum of two given integers 
    public static int max(int a, int b) { 
     return (a > b) ? a : b; 

    } 

    public static int MemoizedCutRod(int price, int lenght) { 

     int[] r = new int[lenght + 1]; 
     for (int i = 1; i <= lenght; i++) { 
      r[i] = 0; 
     } 
     return MemoizedCutRodAux(price, lenght, r); 
    } 

    public static int MemoizedCutRodAux(int price, int lenght, int[] r) { 

     int[] priceTable = new int[11]; 
     priceTable[1] = 1; 
     priceTable[2] = 5; 
     priceTable[3] = 8; 
     priceTable[4] = 9; 
     priceTable[5] = 10; 
     priceTable[6] = 17; 
     priceTable[7] = 17; 
     priceTable[8] = 20; 
     priceTable[9] = 24; 
     priceTable[10] = 30; 

     if (r[lenght] >= 0) { 
      return r[lenght]; 
     } 

     if (lenght == 0) { 
      return 0; 
     } 
     int q = 0; 

     for (int i = 1; i <= lenght; i++) { 
      q = max(q, priceTable[i] + MemoizedCutRodAux(price, lenght, r)); 
      r[lenght] = q; 
     } 
     return q; 
    } 

這段代碼的所有輸出都爲0，但這個代碼的非記憶版本工作。它有什麼問題？這裏是工作代碼：

public class Simple { 

    //finds maximum of two given integers 
    public static int max(int a, int b) { 
     return (a > b) ? a : b; 

    } 

    public static int cormenCutRod(int price, int lenght) { 

     int[] priceTable = new int[11]; 
     priceTable[1] = 1; 
     priceTable[2] = 5; 
     priceTable[3] = 8; 
     priceTable[4] = 9; 
     priceTable[5] = 10; 
     priceTable[6] = 17; 
     priceTable[7] = 17; 
     priceTable[8] = 20; 
     priceTable[9] = 24; 
     priceTable[10] = 30; 

     if (lenght == 0) { 
      return 0; 
     } 
     int q = 0; 
     for (int i = 1; i <= lenght; i++) { 
      q = max(q, priceTable[i] + cormenCutRod(price, lenght - i)); 
     } 

     return q; 
    } 

Answer 1

這應該工作。

static int cutRodM(int lenght) 
    { 

     int[] priceTable = new int[11]; 
     priceTable[1] = 1; 
     priceTable[2] = 5; 
     priceTable[3] = 8; 
     priceTable[4] = 9; 
     priceTable[5] = 10; 
     priceTable[6] = 17; 
     priceTable[7] = 17; 
     priceTable[8] = 20; 
     priceTable[9] = 24; 
     priceTable[10] = 30; 

     int[] mem= new int[lenght+1]; 
     mem[0] = 0; 
     int i, j; 
     //filling the table bottom up 
     for (i = 1; i<=lenght; i++) 
     { 
      int q = 0; 
      for (j = 1; j <= i; j++) 
      q = max(q, priceTable[j] + mem[i-j]); 
      mem[i] = q; 
     } 

     return mem[lenght]; 
    } 

Ideone鏈接：http://ideone.com/OWgrAZ