118. 杨辉三角

解题思路

1. 第一种解法，DP算法，推导状态转移方程
   • a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
   • i == 0 || j == 0 || j == numRows时，为边界
   • 时间复杂度为O（n^{2），空间复杂度为O（n}2）
     2.第二种解法，依然是用状态转移方程，但是不再使用中间变量，直接使用结果变量

解题遇到的问题

1.第一种解法时间没有问题，但是空间消耗太多，二维数组并未全部使用
2.第二种解法，除了结果空间，不再使用其他存储空间

后续需要总结学习的知识点

1.如何达到内存使用方面，也是100%？

image.png

##解法1
class Solution {
    /**
     * @1.DP算法，推导状态转移方程
     *  a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
     *  i == 0 || j == 0 || j == numRows时，为边界
     */
    public List<List<Integer>> generate(int numRows) {
        int[][] a = new int[numRows][numRows];
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if (i == 0 || j == 0 || j == i) {
                    a[i][j] = 1;
                } else {
                    a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
                }
                temp.add(a[i][j]);
            }
            result.add(temp);
        }
        return result;
    }
}

##解法2
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if (i == 0 || j == 0 || j == i) {
                    temp.add(1);
                } else {
                    temp.add(result.get(i - 1).get(j - 1)
                            + result.get(i - 1).get(j));
                }
            }
            result.add(temp);
        }
        return result;
    }
}