【Hot 100 刷题计划】 LeetCode 118. 杨辉三角 | C++ 动态规划题解

LeetCode 118. 杨辉三角 | C 数组模拟与动态规划题解 题目描述题目级别简单给定一个非负整数numRows生成「杨辉三角」的前numRows行。在「杨辉三角」中每个数是它左上方和右上方的数的和。 解题思路数组模拟 / 基础动态规划生成杨辉三角的过程本质上就是一个非常基础的动态规划或递推过程。我们可以将其看作是一个二维数组只是每一行的长度在递增。通过观察杨辉三角的排布规律我们可以总结出两个核心的生成规则边界规则每一行的第一个元素和最后一个元素永远是1。对应代码逻辑当列索引j 0首位或者j i末位时该位置的值赋为1。内部推导规则状态转移方程除首尾元素外内部的任何一个数字都等于它正上方的数字与左上方的数字之和。对应代码逻辑res[i][j] res[i - 1][j - 1] res[i - 1][j]。图解推导过程假设我们要计算第 3 行索引为i 2的中间元素索引为j 1左上方元素第 2 行i - 1 1的第 1 个元素j - 1 0即res[1][0]。右上方正上方元素第 2 行i - 1 1的第 2 个元素j 1即res[1][1]。得出res[2][1] res[1][0] res[1][1]。 C 代码实现classSolution{public:vectorvectorintgenerate(intnumRows){// 初始化外层 vector总共有 numRows 行vectorvectorintres(numRows);for(inti0;inumRows;i){// 动态分配当前行的空间第 i 行有 i 1 个元素res[i].resize(i1);// 遍历当前行的每一个位置for(intj0;ji;j){// 边界条件每一行的第一个和最后一个元素固定为 1if(j0||ji){res[i][j]1;}// 状态转移中间元素 左上方元素 右上方元素else{res[i][j]res[i-1][j-1]res[i-1][j];}}}returnres;}};