个人微信网站建设,动漫网站源码下载,做分类信息网站代码,游戏软件制作公司动态规划基础题#xff0c;当前所在元素来自上一行的两列的值。
题目 从图可以看出#xff0c;每一行的第一个数与最后一个数都是1#xff0c;然后中间的数是来自它左上方和右上方的数的和。当然并不是要打印这个三角形的形状#xff0c;因此可以想到正常的打印方式应该是…动态规划基础题当前所在元素来自上一行的两列的值。
题目 从图可以看出每一行的第一个数与最后一个数都是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 ListListInteger generate(int numRows) {ListListInteger res new ArrayListListInteger();for (int i 0; i numRows; i) {ListInteger row new ArrayListInteger();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;}
}
动态规划找规律写状态转移方程还是很重要的。
