package y2019.Algorithm.array;

import java.util.ArrayList;

import java.util.List;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: GetRow

 * @Author: xiaof

 * @Description: 119. Pascal's Triangle II

 * Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

 * Note that the row index starts from 0.

 * <p>

 * Input: 3

 * Output: [1,3,3,1]

 * <p>

 * 这里和之前的类似，就是获取这个塔的第几行，那么我们每次字需要存上一行，就可以求出下一行数据了

 * a[i,j] = a[i - 1][j-1] + a[i - 1][j]

 * @Date: 2019/7/2 9:13

 * @Version: 1.0

 */

public class GetRow {

    public List<Integer> solution(int rowIndex) {

        List<Integer> preRow = new ArrayList();

        preRow.add(1); //第一行

        List<Integer> curRow = new ArrayList();

        if (rowIndex == 0) {

            return preRow;

        }

        //如果不是第一行

        curRow.add(1);

        for (int i = 1; i <= rowIndex; ++i) {

            //从第二行开始

            curRow = new ArrayList<>();

            for(int j = 0; j < i + 1; ++j) {

                if(j == 0 || j == i) {

                    curRow.add(1);

                } else {

                    curRow.add(preRow.get(j - 1) + preRow.get(j));

                }

            }

            preRow = curRow;

        }

        return curRow;

    }

    public static void main(String args[]) {

        GetRow getRow = new GetRow();

        System.out.println(getRow.solution(0));

    }

}