给定一个索引 k，返回帕斯卡三角形（杨辉三角）的第 k 行。
例如：
给定 k = 3，则返回 [1, 3, 3, 1]
你可以优化你的算法到 O(k) 的空间复杂度吗？
使用递归的方式： Ck[n] = Ck-1[n-1] + Ck-1[n]【超时了】
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>(rowIndex+1);
int half = rowIndex / 2;
if(rowIndex == 1){
result.add(1);
result.add(1);
return result;
}
for(int i=0;i<rowIndex + 1;i++){
//如果是另一半，则取对称元素
if(i > half) {
result.add(result.get(rowIndex - i));
}
else{
result.add(getNum(rowIndex, i));
}
}
return result;
}
//索引k， 第n个
private Integer getNum(int k, int n) {
if(k == 0 || k == 1){
return 1;
}
if(n == 0 || n == k) {
return 1;
}
return getNum(k-1, n-1) + getNum(k-1, n);
}
}
以上之所以出现超时，是因为递归调用时存在多次重复调用。
比如在计算getNum(10, 3)时会发起调用：
递归.png
如上图所示，getNum(8,2),getNum(7,1)和getNum(7,2)会调用多次，越到后面，重复调用的递归会更多，如果把这些递归调用的结果保存下来，效果会不会更好呢？
class Solution {
private Map<String,Integer> cache = new HashMap<String, Integer>();
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>(rowIndex+1);
int half = rowIndex / 2;
if(rowIndex == 1){
result.add(1);
result.add(1);
return result;
}
for(int i=0;i<rowIndex + 1;i++){
//如果是另一半，则取对称元素
if(i > half) {
result.add(result.get(rowIndex - i));
}
else{
result.add(getNum(rowIndex, i));
}
}//0 1 2 3 1
return result;
}
//索引k， 第n个
private Integer getNum(int k, int n) {
if(cache.get(k + ":" + n) != null){
return cache.get(k + ":" + n);
}
if(k == 0 || k == 1){
return 1;
}
if(n == 0 || n == k) {
return 1;
}
int r = getNum(k-1, n-1) + getNum(k-1, n);
cache.put(k + ":" + n, r);
return r;
}
}
结果很nice, Leetcode给的结论是【4ms】，然而这个结果却是所有答案中耗时最大的，难道还有优化的地步。
杨辉三角规律：
第n行第1个数： 1
第n行第2个数：1×(n-1)
第n行第3个数：1×(n-1)×(n-2)/2
第n行第4个数: 1×(n-1)×(n-2)/2*(n-3)/3
用索引讲：
第k索引行第0索引数：1
第k索引行第1索引数：1×k
第k索引行第2索引数：1×k×(k-1)/2
第k索引行第3索引数：1×k×(k-1)/2×(k-2)/3
所以最终答案： 【耗时1ms】
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>(rowIndex+1);
int half = rowIndex / 2;
if(rowIndex == 1){
result.add(1);
result.add(1);
return result;
}
for(int i=0;i<rowIndex + 1;i++){
if(i == 0){
result.add(1);
continue;
}
//如果是另一半，则取对称元素
if(i > half) {
result.add(result.get(rowIndex - i));
}
else{
result.add(Double.valueOf(1.0 * result.get(i-1) * (rowIndex - (i-1)) / i).intValue());
}
}//0 1 2 3 1
return result;
}
}
总结： 杨辉三角每行元素不仅和上一行有关系，同一行元素之间的关系也颇为密切。而递归则是采用第一种方案，不用缓存在计算大数时会出现超时，而第二种方案则非常轻松实现。
