LeetCode 热门题目第100题 | 动态规划（DP系列）

目录

1 70. 爬楼梯

1.1 核心理念

1.2 权威解答

2 118. 杨辉三角

3 198. 打家劫舍

---

新手解题，采用的编程语言为 C++

1 70. 爬楼梯

【核心理念：将整体问题划分为多个局部问题。

• 整体问题：抵达第五层楼的路径总数
• 局部问题：抵达第四层楼的路径总数、抵达第三层楼的路径总数
• 整体问题 = 局部问题 1 + 局部问题 2

鉴于题目规定每次只能攀登一层或两层台阶，因此所涉及的局部问题仅包含两个。

1.1 基本思路

假定依据英国的算法标准，需要攀登六层楼，具体示意图如下：

【采用一个名为 dp 的数组，用于记录抵达每一层楼的不同路径数量。

鉴于从 4 楼或 3 楼均可到达 5 楼，因此抵达 5 楼的路径总数等于抵达 4 楼的路径数与抵达 3 楼的路径数之和，即 dp[5] = dp[4] + dp[3]，依此类推。

值得注意的是，对于第 0 层和第 1 层而言，由于仅存在一种方式可以抵达它们，因此可以直接将对应的值设为 1。

不幸的是，上述方