Saturday, August 8, 2015

LeetCode OJ - Pascal's Triangle II

Problem:

Solution:

Note the recurrence $_nC_r = \frac{n!}{r!(n-r)!} = \frac{n!(n-r+1)}{r(r-1)!(n-r+1)!} = \frac{n-r+1}{r}\frac{n!}{(r-1)!(n-r+1)!} = \frac{n-r+1}{r}\frac{n!}{(r-1)!(n-(r-1))!} = \frac{n-r+1}{r}_nC_{(r-1)}$.

With that, we can simply compute the values one by one from left to right!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/pascals-triangle-ii/

#include "LEET_PASCALS_TRIANGLE_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PASCALS_TRIANGLE_II
{
class Solution
{
public:
vector<int> getRow(int rowIndex)
{
vector<int> result;
result.resize(rowIndex + 1);
result[0] = 1;
for (int i = 1; i <= rowIndex; i++)
{
long long temp = result[i - 1];
temp = temp * (rowIndex + 1 - i) / i;
result[i] = (int)temp;
}
return result;
}
};
};

using namespace _LEET_PASCALS_TRIANGLE_II;

int LEET_PASCALS_TRIANGLE_II()
{
Solution solution;
for (int i = 1; i <= 10; i++)
{
vector<int> result = solution.getRow(i);
for (unsigned int j = 0; j < result.size(); j++)
{
cout << result[j] << " ";
}
cout << endl;
}
return 0;
}