You're close, you want to use dynamic programming to solve this problem. I think recursive calls to printRow is cheating.
dp[j] += dp[j - 1] comes from the relationship that pascal[r][c] = pascal[r - 1][c] + pascal[r - 1][c - 1]
Before computing the new value we can assert that dp[j] == pascal[i - 1][j] and that dp[j - 1] == pascal[i - 1][j] because we are iterating backwards, therefore to calculate the value of pascal[i][j] and put it in the variable dp[j] we simply need to add dp[j - 1]
CODE
public void printPascal(int rows)
{
int [] dp = new int[rows];
//Set intial array to {1, 0, 0, ... 0}
dp[0] = 1;
//Print first row
System.out.println(1);
//Calculate and print each row
for(int i = 1; i < rows; i++)
{
//Calculate new row values
for(int j = i; j > 0; j--)
{
dp[j] += dp[j - 1];
}
//Print new row
for(int j = 0; j <= i; j++)
{
System.out.print("" + dp[j] + " ");
}
System.out.println();
}
}
This post has been edited by msg555: 14 Feb, 2007 - 08:00 AM
| 