/**
*
*/
package com.kant.algos.dynamicProgramming;
import java.util.Arrays;
/**
* @author shashi
*
*/
public class PascalSTriangle {
int maxRow = 100;
int maxColumn = 100;
int dpStore[][] = null;
public PascalSTriangle() {
init(maxRow, maxColumn);
}
/**
*
* @param mRow
* @param mColumn
*/
public PascalSTriangle(int mRow, int mColumn) {
init(mRow, mColumn);
}
/**
* @param args
*/
public static void main(String[] args) {
PascalSTriangle pascalSTriangle = new PascalSTriangle(5, 5);
for (int r = 0; r < 5; r++) {
for (int c = 0; c <= r; c++)
System.out
.print(" " + pascalSTriangle.callPascalDp(true, r, c));
System.out.println();
}
}
/**
* to switch between non-dp and dp solution.
*
* @param row
* @param column
* @return
*/
public int callPascalDp(boolean dptrue, int row, int column) {
if (dptrue)
return pascalDp(row, column);
else
return pascal(row, column);
}
/**
*
*/
private void init(int row, int column) {
if (dpStore == null) {
dpStore = new int[row][column];
for (int[] x : dpStore) {
Arrays.fill(x, -1);
}
}
}
/**
*
* @param row
* @param column
* @return
*/
private int pascalDp(int row, int column) {
if ((row < 0 || column < 0) || (row >= 0 && column > 1 + row)) {
dpStore[row][column] = 0;
return 0;
}
else if (row == column || row == 0) {
dpStore[row][column] = 1;
return dpStore[row][column];
}
int result = 0;
if (dpStore[row][column] == -1) {
if (row > 0 && column > 0) {
result = (dpStore[row - 1][column - 1] == -1) ? pascalDp(
row - 1, column - 1) : dpStore[row - 1][column - 1];
}
if (row > 0 && column >= 0) {
result += (dpStore[row - 1][column] == -1) ? pascalDp(row - 1,
column) : dpStore[row - 1][column];
}
dpStore[row][column] = result;
}
return dpStore[row][column];
}
/**
* Non dynamic programming solution.
*
* Store each pascal(r,c) call into a table[r][c] .
*
* @param row
* @param column
* @return
*/
public int pascal(int row, int column) {
if ((row < 0 || column < 0) || (row >= 0 && column > 1 + row))
return 0;
if (row == column || row == 0)
return 1;
System.out.println("pascal(" + (row - 1) + "," + (column - 1)
+ ") and " + "pascal(" + (row - 1) + "," + (column) + ")");
return pascal(row - 1, column - 1) + pascal(row - 1, column);
}
}