Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3, Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

s思路： 1. 假設(shè)我們需要k=5,我們已經(jīng)得到k=4的樣子，即：[1,3,3,1,1],如何從k=4計(jì)算除k=5?我們知道[3,3]都要使用兩次，從左往右遍歷時(shí)，1+3=4需要放在3這個(gè)位置，但3還要使用一次，所以不能放。也就是說我們需要額外的空間來hold計(jì)算結(jié)果；由于3使用的次數(shù)固定，即：1+3，還有3+3,但是計(jì)算順序是1+3先進(jìn)行還是3+3先進(jìn)行都無所謂。所以，我們讓3+3先進(jìn)行看看，即：從右往左遍歷：3+3結(jié)果為6，直接放在原來3的位置，1+3=4也直接放在3的位置。 2. 一個(gè)小trick。遍歷順序從左往右—->從右往左。但是里面的深的含義還是有趣味！