---

前言

一个本硕双非的小菜鸡，备战24年秋招，计划刷完hot100和剑指Offer的刷题计划，加油！
根据要求，每一道题都要写出两种以上的解题技巧。

一、70. 爬楼梯（HOT100）

70. 爬楼梯
Note：动态规划解题

class Solution {
public:int climbStairs(int n) {if (n < 2) return n;//1.确定dp数组//n级台阶有多少种方法vector<int> dp(n);//2.确定dp公式//dp[n] = dp[n - 1] + dp[n - 2];//3.确定dp数组初始化dp[0] = 1;dp[1] = 2;//4.确定遍历顺序for (int i = 2; i < n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n - 1];}
};

Note：数学方法，通过递推数列的通向公式解题

class Solution {
public:int climbStairs(int n) {double sqrt5 = sqrt(5);double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);return (int)round(fibn / sqrt5);}
};

二、118. 杨辉三角（HOT100）

118. 杨辉三角

Note：动态规划解题

class Solution {
public:vector<vector<int>> generate(int numRows) {//1.确定dp数组//每一层具体的数值vector<vector<int>> dp(numRows);//2.确定dp公式//dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];//3.确定dp数组初始化//所有节点先全部设置为1for (int i = 0; i < numRows; i++) {dp[i] = vector<int>(i + 1, 1);}//4.确定遍历顺序for (int i = 2; i < numRows; i++) {for (int j = 1; j < i; j++) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}}return dp;}
};

Note：数学方法（其实跟动规没啥区别）

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ret(numRows);for (int i = 0; i < numRows; i++) {ret[i].resize(i + 1);ret[i][0] = ret[i][i] = 1;for (int j = 1; j < i; j++) {ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];}}return ret;}
};

总结

祝大家都能学有所成，找到一份好工作！