自己做的网站加载慢的原因,网站关键词指数查询,织梦体育网站模板,宜都网站建设118、杨辉三角 状态转移方程
我们还是老套路起手#xff1a;先列出状态转移方程。
base case
每行的第一个和最后一个数字都是1
明确状态
“原问题或子问题中变化的变量”
此处的“状态”就是某一位置的数字大小
在此题中#xff0c;每一个数的“状态” 是由其左上方…118、杨辉三角 状态转移方程
我们还是老套路起手先列出状态转移方程。
base case
每行的第一个和最后一个数字都是1
明确状态
“原问题或子问题中变化的变量”
此处的“状态”就是某一位置的数字大小
在此题中每一个数的“状态” 是由其左上方和右上方的数的“状态”转移而来
确定选择
“导致“状态”产生变化的行为”
行和列的变化导致了数字的变化。所以“选择”是 行和列 的变化。 自下而上的迭代解法
遍历所有状态去做选择
class Solution {public ListListInteger generate(int numRows) {//定义一个二维数组用于存放返回值ListListInteger ret new ArrayListListInteger();//外层for循环遍历行for (int i 0; i numRows; i) {ListInteger row new ArrayListInteger();//内层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;}
}
