题解 | #杨辉三角(二)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        // write code here
        
        return getRow(new HashMap<Integer, int[]>(), num);
    }


  	/**
	*  return 返回第num行的杨辉三角数组
	*  map：保存每一行的数据，key为行号， value为行的数组
	*  num: 行号
	**/
    private int[] getRow(Map<Integer, int[]> map, int num){

        if(num == 0) {
		  //递归终止条件
            return new int[]{1};
        }

	  	//初始化数组
        int[] result = new int[num + 1];

	  	//第一个数字一定是1
        result[0] = 1;
        
        for(int j = 1; j < num; j++){

		  	//先从map获取上一行的数组
            int[] last =  map.get(num - 1);
            if(last == null) {
			  //没有时采用递归计算获取
                last =  getRow(map, num - 1);
            }

		  	//累加上一行数据
            result[j] = last[j - 1] + last[j];
        }

	  	//最后一个数字一定是1
        result[num] = 1;
		//保存计算过的数据
        map.put(num, result);

        return result;
    }
}