一.爬楼梯
leetcode 746.使用最小花费爬楼梯
（1）递归
思路：
1.分析状态
题目要求从0爬到第n个台阶，我们不妨想想到第i个台阶是什么样的？
令f(i)是到第i个台阶的最小花费，那么他该怎么表达呢？
题目中说如果你支付台阶的费用，那么你可以向上爬1或2个台阶
我们不妨想一下递归的过程
那么第i个台阶可以是第i-1个台阶上来的，也可以是第i-2个台阶上来的，那么就很明朗了，两种情况取最小值即可.
可以得出f(i) = min(f(i - 1) + cost[i - 1],f(i - 2) + cost[i - 2]);这个式子。
2.边界情况
（这里自顶向下递归）
当i <= 1的时候无台阶可爬(起点)，返回0
代码：
class Solution { public: int minCostClimbingStairs(vector<int>& cost){ int n = cost.size(); auto dp = [&](this auto&& dp,int i){ if(i <= 1){ return 0; } return min(dp(i - 1) + cost[i - 1],dp(i - 2) + cost[i - 2]); }; return dp(n); } }; 嗯在leetcode上写的时候运行能通过,可是提交的时候显示超出时间限制，怎么办呢？？
（2）递归优化->记忆化搜索
注意：调用f(i-1)的时候又会产生两个分支：f(i-2),f(i-3),而f(i-2)之前在调用f(i)的时候计算过了......以此类推，在递归的过程中会不断产生相同的分支。因此我们可以将这些分支全部"剪"掉。减少不必要的计算。
具体做法：
创建一个数组memo，并设置不会出bug的初始值，以i当访问该数组的下标，以f(i)作为memo[i]存的值，在每次访问的时候发现f(i)的量不等于初始值的时候返回memo[i]的值即可。
代码：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> memo(n + 1,-1); auto dp = [&](this auto&& dp,int i){ if(i <= 1){ return 0; } int& ret = memo[i]; if(ret > -1){ return ret; } return ret = min(dp(i - 1) + cost[i - 1],dp(i - 2) + cost[i - 2]); }; return dp(n); } };（int& ret类似于c语言的指针，&是引用符，赋值的时候不用像指针一样解引用也能存里面）
(3)转化成递推
递推与递归本质是同一问题的两种表现形式，递推从已知向未知逐步求解，递归从未知向已知回溯。两者可通过状态定义与转移方程统一。
递推从边界正向推导，逐步填充状态。
思路：
1.找式子
只不过这次变成递推式，有了递归的经验，很容易便能找到递推式：
f[i]=min(f[i−1]+cost[i−1],f[i−2]+cost[i−2])；
2.递推入口：
我们自底向上计算，题目告诉我们可以从第0，1个台阶向上走，因此f[0] = 0;f[1] = 0;
3.返回值：
f[i]表示前i个的最小值，那么f[n]表示前n-1个最小值，返回f[n]
代码：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> f(n + 1); for (int i = 2; i <= n; i++) { f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]); } return f[n]; } };（看有多少种状态决定开多大的数组）
二丶打家劫舍问题
leetcode 198. 打家劫舍
（1)递归（自动记忆化了哈）
思路：
1.状态表示
设f(i)是前i个能偷到的最大金额
怎么来的？假设前一次行动没偷，那可以是从i-1来的，如果是这样，那这次就不能再偷了。假设前一次行动偷了，那只能是i-2或者之前来的。又因为nums[i] >= 0那么我们尽可能偷就行了，只考虑这两种情况。
可以列出：f(i) = max(f(i - 1),f(i - 2)+nums[i]);
2.递归边界
当i<0的时候没房子能偷，返回0
3.入口
自顶向下算，因此是从n - 1开始。
代码：
class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); vector<int> memo(n,-1); auto dp = [&](this auto&& dp,int i){ if(i < 0){ return 0; } int& ret = memo[i]; if(ret > -1){ return ret; } return ret = max(dp(i - 2) + nums[i],dp(i - 1)); }; return dp(n - 1); } };（2）递推：
思路：
1.式子：
从上一集不难看出来式子为f[i] = max(f[i - 1],f[i - 2] + nums[i]);
2.入口：
不难发现递归最后遍历到的东西：f(-1),f(-2)，可这玩意在数组里指定越界！怎么办？
数组整体往后移两位，令f(0) = 0,f(1) = 0即可。
3.大小：
从上分析不难得出大小是n + 2(考虑俩越界的）
代码：
class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); vector<int> f(n + 2); for(int i = 2; i < n + 2; i++){ f[i] = max(f[i - 1],f[i - 2] + nums[i - 2]); } return f[n + 1]; } };(nums里那个i还是那个i，没跟着f扩大，因此访问的时候要-2）
三丶最大子数组和
leetcode 53. 最大子数组和
(1)递归
思路：
1.状态表示
题目要求我们求出子数组的最大和，我们设f(i)是第i个元素及其之前所构成的最大和的子数组，那么f(i-1)就是第i-1及其之前元素所构成的最大和的子数组，对于f(i-1),我们有选或不选两种情况，而对于nums[i]，我们必须选（因为子数组不能为空）。怎么思考选或者不选呢？当f(i-1)小于0的时候不选，因为选他比不选他还小，当f(i-1) <= 0的时候就可以选了（要么不变要么更大）。由此，我们可以列出式子：
f(i) = max(f(i - 1),0) + nums[i];
2.递归边界：
当i < 0的时候不可能存在子数组，返回INT_MIN。
3.入口：
自顶向下算。注意：因为是子数组，所以在哪里结尾都有可能，我们得枚举从0到n-1所有可能的结尾，也就是枚举入口。
4.代码：
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> memo(n + 1,INT_MIN); auto dp = [&](this auto&& dp,int i){ if(i < 0){ return INT_MIN; } int& ret = memo[i]; if(ret != INT_MIN){ return ret; } return ret = max(dp(i - 1),0) + nums[i]; }; int ans = INT_MIN; for(int i = 0; i < n; i++) { ans = max(ans, dp(i)); } return ans; } };（这种用递归实现会麻烦一点）
（2）递推
思路：
（其实递归那里基本都想完了）
1.式子：
由上可得，f[i] = max(f[i - 1],0) + nums[i];
2.入口：
由于子数组不能为空，所以入口是nums[i]。
3.大小：
从n到0，开大小为n的数组
4.代码：
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> f(n); f[0] = nums[0]; for (int i = 1; i < nums.size(); i++) { f[i] = max(f[i - 1], 0) + nums[i]; } return ranges::max(f); } }; （由于数组会存下每一种结尾可能的最大值,所以我们只用往后推就行，结果交给max函数）
总结
定义状态：明确
dp(i)或f[i]的含义。写出转移方程：分析状态之间的关系。
确定边界与入口：确保递推/递归有起点。
选择实现方式：递归（+记忆化）或递推，根据问题特点选择。
避免模板化：理解本质，灵活应用
