【动态规划】LC 118.杨辉三角

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接118.杨辉三角2、题目描述二、个人思路整理1、思路分析dp[i][j]代表杨辉三角第i行第j列的元素值下标均从0开始。状态转移方程每一行的首尾两端均为1即dp[i][0]1dp[i][i]1。对于行内的中间元素0ji其值等于上一行相邻两个元素之和即dp[i][j]dp[i-1][j-1]dp[i-1][j]。复杂度分析时间复杂度O ( numRows 2 ) O(\text{numRows}^2)O(numRows2)一共需要计算1 2 ⋯ numRows numRows ( numRows 1 ) 2 1 2 \dots \text{numRows} \frac{\text{numRows}(\text{numRows} 1)}{2}12⋯numRows2numRows(numRows1)​个数字。空间复杂度O ( 1 ) O(1)O(1)返回值所需的存储空间除外。2、解题代码classSolution{public:vectorvectorintgenerate(intnumRows){vectorvectorintdp(numRows);//开辟含numRows个空vector的dp数组for(inti0;inumRows;i){dp[i].resize(i1,1);// 第i行有i1个元素先全部初始化为1for(intj1;ji;j){// 中间元素等于上一行相邻两数之和dp[i][j]dp[i-1][j-1]dp[i-1][j];}}returndp;}};三、知识风暴vector赋值vectorint dp(n, val);有参构造函数分配n个元素的内存空间并将每个元素都初始化为val如果省略第二个参数如vectorint dp(n);默认会用类型的默认值填充对于int就是0 00。dp.resize(n, val)成员方法用于调整一个已经存在的vector的大小改变其size()。行为规则当n 当前 size n \text{当前 size}n当前size数组扩容到n nn多出来的那些新元素会被赋值为val若省略val则为0 00。当n 当前 size n \text{当前 size}n当前size数组截断到前n nn个元素超出部分被直接丢弃。当n 当前 size n \text{当前 size}n当前size什么也不做原有元素的值保持不变。vectorvectorint dp(n)会创建n nn个vectorint每个vectorint调用其默认构造函数当vectorint被默认初始化时默认构造函数vectorint()产生的是一个size 0的空动态数组。