安阳网站建设方案贵阳大数据论坛

动态规划基础题，当前所在元素来自上一行的两列的值。

题目

从图可以看出，每一行的第一个数与最后一个数都是1，然后中间的数是来自它左上方和右上方的数的和。当然并不是要打印这个三角形的形状，因此可以想到正常的打印方式应该是从每一行的左边往右边打的，默认的打印与循环的三角形的每一行每一列应该是这样的。

1
1 2 1
1 3 3 1
1 4 6 4 1

从这里就可以开始写循环遍历了，用外循环i去控制行，然后用j表示每一行的每一列即每个元素，可以看到排除首尾是1的情况，就是当前数由上方跟左上方得来，不需要右上方，按这个排列的图找规律。然后排去首尾特殊的数，还发现到，每一行需要dp的数量跟当前行号是一致的，注意这里的行号从0开始，即第一行有一个数为2，第二行有两个数3、3等等。然后就可以依照这些规律写dp了，这里用了嵌套动态数组去加每一行每一列，里面的数组对应每一行的数组，然后外层即一个大的list了。

状态转移方程为：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，这里的get是用来读取arraylist的值。

时间复杂度：O(numRows^2)，空间复杂度：O(1)。

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> res = new ArrayList<List<Integer>>();for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<Integer>();for (int j = 0; j <= i; j++) {  //每一行的数量是行号if (j == 0 || j == i) {row.add(1);//每一行的首尾} else {row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));//由上一个跟上一个的附近一个得来}}res.add(row);//加入每一行}return res;}
}

动态规划找规律写状态转移方程还是很重要的。