# Pascal's Triangle (*So close, need help finishing*)

Page 1 of 1

## 2 Replies - 16034 Views - Last Post: 27 November 2009 - 09:31 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=23942&amp;s=d5e060a3f1109778b53092dbcd9c2f1b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 prelic

• New D.I.C Head

Reputation: 0
• Posts: 26
• Joined: 13-February 07

# Pascal's Triangle (*So close, need help finishing*)

Posted 13 February 2007 - 08:54 PM

I have to print pascal's triangle given a user-inputted row number.

here are the constraints:
-cannot use 2d array
-cannot use more than 1 array
-cannot use temp values

here is what i have come up with so far:
-initialize all to 1
-need 2 nested for loops

i know its SO close to this, just need a push

```public static void calculate(int[] triangle)
{

for(int x = triangle.length - 1; x>= 1; x--)
{

for(int y= 1; y < triangle.length; y++)
{
triangle[y] = triangle[y] + triangle[y-1];
printRow(triangle);
}

}
}

```

Is This A Good Question/Topic? 0

### #5 msg555

• D.I.C Head

Reputation: 9
• Posts: 136
• Joined: 04-May 06

## Re: Pascal's Triangle (*So close, need help finishing*)

Posted 14 February 2007 - 08:46 AM

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]

```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 February 2007 - 09:00 AM

Was This Post Helpful? 1

### #9 ynnorj

• New D.I.C Head

Reputation: 2
• Posts: 3
• Joined: 27-November 09

## Re: Pascal's Triangle (*So close, need help finishing*)

Posted 27 November 2009 - 09:31 AM

Here's a little tricky formula without even using an array at all...
This might be a little too late, but hope this would help someone.

```for(int i = 0; i < n; i++) {
for(int j = 0, x = 1; j <= i; j++) {
System.out.print(x + " ");
x = x * (i - j) / (j + 1);
}
System.out.println();
}
```

Was This Post Helpful? 1

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }