规划实现斐波那契+不同路径问题

一、斐波那契数列（动态规划版）

1. 完整可运行代码

#include<iostream>#include<vector>usingnamespacestd;// 动态规划五部曲实现斐波那契数列classSolution{public:intfib(intn){// Step1：确定dp[i]含义：dp[i]表示第i个斐波那契数vector<int>dp;dp.resize(n+1);// 初始化dp数组大小，避免下标越界// Step3：dp数组初始化 + 边界条件处理if(n==0)return0;// 标准斐波那契：fib(0)=0if(n==1)return1;// 标准斐波那契：fib(1)=1dp[0]=0;dp[1]=1;// Step4：遍历顺序：从前向后（依赖前两个数，必须顺序遍历）// Step2：递推公式：dp[i] = dp[i-1] + dp[i-2]for(inti=2;i<=n