package dp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author: wei1
 * @Date: Create in 2018/12/24 0:48
 * @Description: 这个DP难在使用O(K)的空间复杂度，从后往前覆盖dp数组，使得二位的dp数组通过覆盖达到一维
 * Given an index k, return the k th row of the Pascal's triangle.
 * <p>
 * For example, given k = 3,
 * Return[1,3,3,1].
 * <p>
 * Note:
 * Could you optimize your algorithm to use only O(k) extra space?
 */
public class PascalTriangle {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> result = new ArrayList<>();
        if (rowIndex < 0) {
            return result;
        }
        result.add(1);
        //这里从1开始，因为第一层已经放进去了就是1
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j > 0; j--) {
                result.set(j, result.get(j - 1) + result.get(j));
            }
            //每次覆盖了前面的dp数组后需要往本层末尾加一个1
            result.add(1);
        }
        return result;
    }

    @Test
    public void test() {
        ArrayList<Integer> row = getRow(1);
        System.out.println(Arrays.toString(row.toArray()));
    }
}