document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /**
  2.  *
  3.  */
  4. package com.kant.algos.dynamicProgramming;
  5.  
  6. import java.util.Arrays;
  7.  
  8. /**
  9.  * @author shashi
  10.  *
  11.  */
  12. public class PascalSTriangle {
  13.     int maxRow = 100;
  14.     int maxColumn = 100;
  15.     int dpStore[][] = null;
  16.  
  17.     public PascalSTriangle() {
  18.         init(maxRow, maxColumn);
  19.     }
  20.  
  21.     /**
  22.      *
  23.      * @param mRow
  24.      * @param mColumn
  25.      */
  26.     public PascalSTriangle(int mRow, int mColumn) {
  27.         init(mRow, mColumn);
  28.     }
  29.  
  30.     /**
  31.      * @param args
  32.      */
  33.     public static void main(String[] args) {
  34.         PascalSTriangle pascalSTriangle = new PascalSTriangle(5, 5);
  35.         for (int r = 0; r < 5; r++) {
  36.             for (int c = 0; c <= r; c++)
  37.                 System.out
  38.                         .print(" " + pascalSTriangle.callPascalDp(true, r, c));
  39.             System.out.println();
  40.         }
  41.  
  42.     }
  43.  
  44.     /**
  45.      * to switch between non-dp and dp solution.
  46.      *
  47.      * @param row
  48.      * @param column
  49.      * @return
  50.      */
  51.     public int callPascalDp(boolean dptrue, int row, int column) {
  52.         if (dptrue)
  53.             return pascalDp(row, column);
  54.         else
  55.             return pascal(row, column);
  56.     }
  57.  
  58.     /**
  59.      *
  60.      */
  61.     private void init(int row, int column) {
  62.         if (dpStore == null) {
  63.             dpStore = new int[row][column];
  64.             for (int[] x : dpStore) {
  65.                 Arrays.fill(x, -1);
  66.             }
  67.         }
  68.     }
  69.  
  70.     /**
  71.      *
  72.      * @param row
  73.      * @param column
  74.      * @return
  75.      */
  76.     private int pascalDp(int row, int column) {
  77.         if ((row < 0 || column < 0) || (row >= 0 && column > 1 + row)) {
  78.             dpStore[row][column] = 0;
  79.             return 0;
  80.         }
  81.  
  82.         else if (row == column || row == 0) {
  83.             dpStore[row][column] = 1;
  84.             return dpStore[row][column];
  85.         }
  86.  
  87.         int result = 0;
  88.         if (dpStore[row][column] == -1) {
  89.             if (row > 0 && column > 0) {
  90.                 result = (dpStore[row - 1][column - 1] == -1) ? pascalDp(
  91.                         row - 1, column - 1) : dpStore[row - 1][column - 1];
  92.             }
  93.             if (row > 0 && column >= 0) {
  94.                 result += (dpStore[row - 1][column] == -1) ? pascalDp(row - 1,
  95.                         column) : dpStore[row - 1][column];
  96.             }
  97.             dpStore[row][column] = result;
  98.  
  99.         }
  100.         return dpStore[row][column];
  101.  
  102.     }
  103.  
  104.     /**
  105.      * Non dynamic programming solution.
  106.      *
  107.      * Store each pascal(r,c) call into a table[r][c] .
  108.      *
  109.      * @param row
  110.      * @param column
  111.      * @return
  112.      */
  113.     public int pascal(int row, int column) {
  114.         if ((row < 0 || column < 0) || (row >= 0 && column > 1 + row))
  115.             return 0;
  116.         if (row == column || row == 0)
  117.             return 1;
  118.         System.out.println("pascal(" + (row - 1) + "," + (column - 1)
  119.                 + ") and " + "pascal(" + (row - 1) + "," + (column) + ")");
  120.         return pascal(row - 1, column - 1) + pascal(row - 1, column);
  121.  
  122.     }
  123.  
  124. }
');