118、杨辉三角

状态转移方程

我们还是老套路起手：先列出状态转移方程。 

base case

每行的第一个和最后一个数字都是1

明确状态

“原问题或子问题中变化的变量”

此处的“状态”就是某一位置的数字大小

在此题中，每一个数的“状态” 是由其左上方和右上方的数的“状态”转移而来

确定选择

“导致“状态”产生变化的行为”

行和列的变化导致了数字的变化。所以“选择”是 行和列 的变化。

自下而上的迭代解法

遍历所有状态去做选择 

class Solution {public List<List<Integer>> generate(int numRows) {//定义一个二维数组用于存放返回值List<List<Integer>> ret = new ArrayList<List<Integer>>();//外层for循环遍历行for (int i = 0; i < numRows; ++i) {List<Integer> row = new ArrayList<Integer>();//内层for循环遍历列for (int j = 0; j <= i; ++j) {//base caseif (j == 0 || j == i) {row.add(1);} else {//列出状态转移方程row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));}}ret.add(row);}return ret;}
}