【小白笔记】杨辉三角

杨辉三角（Pascal’s Triangle）是一个非常经典的数学和算法问题。它的核心规律非常直观：每一行的首尾都是 1，其余位置的数值等于它正上方和左上方两个数值之和。

1. 算法思路

2. 代码实现 (Python)

classSolution:defgenerate(self,numRows:int)->List[List[int]]:triangle=[]forrow_numinrange(numRows):# 每一行的长度等于 ![当](https://i-blog.csdnimg.cn/direct/2578b7f30ccb4fc28f466c8857b841e2.png)前行索引+1# 初始化为一个全为 1 的列表row=[1]*(row_num+1)# 只有从第 3 行（索引为 2）开始，才有中间元素需要计算forjinrange(1,row_num):# 中间元素 = 上一行的左上方 + 正上方row[j]=triangle[row_num-1][j-1]+triangle[row_num-1][j]triangle.append(row)returntriangle

将“杨辉三角”放入**划分型动态规划（Partition DP）**的框架下分析是一个非常深刻的视角。虽然杨辉三角本身较为简单，但它是理解“状态转移依赖于上一层划分结果”的绝佳案例。

🚀 划分型 DP 通用模板代码 (杨辉三角版)

defpartition_dp_template(numRows):# 1. 初始化 DP 表 (处理边界)# 这里的 dp[i] 代表对第 i 层的划分结果dp=[[1]*(i+1)foriinrange(numRows)]# 2. 外部循环：枚举规模 (自底向上，从第 3 层开始)foriinrange(2,numRows):# 3. 内部循环：枚举当前规模下的所有划分点/位置forjinrange(1,i):# 4. 状态转移：利用重叠子问题的结果# 当前决策 = 依赖于前一阶段已计算出的子状态dp[i][j]=dp[i-1][j-1]+dp[i-1][j]# 5. 返回最终状态returndp

💡 划分型 DP 的攻克口诀

1. 分哪儿：枚举最后一个划分点 。
2. 看前面：当前最优 = + [0, k-1] 的子问题的解。
3. 记下来：用数组存储已计算的划分结果，避免重复。