一、题目二、做题思路2.1 状态表示核心基础状态表示即明确dp表中每个元素所代表的含义。其来源通常有三直接依据题目要求、结合经验对题目进行抽象、或在分析过程中提炼重复子问题。本题中题目已明确要求数组下标i对应第i个泰波那契数因此我们定义dp[i]表示第i个泰波那契数的值。这是后续推导的基石必须首先确定。2.2 状态转移方程关键难点状态转移方程描述了dp[i]与前面若干状态之间的递推关系来源于题目给出的递推公式。本题直接依据泰波那契数列的定义dp[i] dp[i-1] dp[i-2] dp[i-3]其中i ≥ 3。该方程将大问题拆解为规模更小的子问题是整个动态规划过程的核心纽带。2.3 初始化边界防护初始化是为了保证填表过程中数组访问不越界同时为递推提供起始条件。由于状态转移方程需要用到前三个状态当i 3时无法通过方程计算因此必须单独给出初始值。本题题目已明确dp[0] 0dp[1] 1dp[2] 1。这些初始值是递推的“种子”是正确计算的必要前提。2.4 填表顺序递推方向填表顺序取决于当前状态所依赖的前驱状态必须保证计算某一状态时其所需的所有前置状态均已就绪。本题中dp[i]依赖i-1、i-2、i-3均小于i因此采用从左到右即下标从小到大的顺序依次填充dp表可确保每次计算时所需数据已经完备。2.5 返回值目标映射返回值即最终需要向调用者输出的结果由题目要求与状态表示共同决定。本题要求返回第n个泰波那契数而dp[n]正好表示该值因此直接返回dp[n]。若n小于初始边界则直接返回对应的初始值避免越界访问。三、代码#include vector using namespace std; class Solution { public: int tribonacci(int n) { //3.初始化 if (n 0) return 0; if (n 1 || n 2) return 1; vectorint dp(n 1);//1.状态表示一个下标对应一个Tn元素 //3.初始化dp表 dp[0] 0, dp[1] 1, dp[2] 1; //2.状态转移方程 dpn dpn-1 dpn-2 dpn-3 //4.填表顺序 for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2] dp[i - 3]; } //5.返回值 return dp[n]; } };四、流程图五、题目六、做题思路6.1 状态表示核心基础本题要求计算到达第i级台阶的所有不同走法总数。因此定义dp[i]表示从地面第 0 级走到第i级台阶的方法数。该定义直接来源于题目要求且以位置为结尾进行统计是后续推导的出发点。6.2 状态转移方程关键难点小孩一次可以上1 阶、2 阶或 3 阶那么到达第i级台阶的最后一步可能来自i-1、i-2或i-3。由于这三种方式是互斥且完备的所以总方法数等于三者之和dp[i] dp[i-1] dp[i-2] dp[i-3]其中i ≥ 4。同时根据示例可验证初始值dp[1]1、dp[2]2、dp[3]4与递推公式吻合。6.3 初始化边界防护递推公式依赖前三个状态因此i1,2,3必须手动赋值dp[1] 1仅 1 步dp[2] 211 或 2dp[3] 4111、12、21、3。此外题目提示结果可能很大需对100000007即1e87取模每次相加后及时取模防止溢出。6.4 填表顺序递推方向计算dp[i]必须依赖dp[i-1]、dp[i-2]、dp[i-3]这些下标均小于i。因此必须从左到右即下标从小到大依次填充dp表保证每个状态计算时其所有前置状态均已就绪。6.5 返回值目标映射题目要求返回第n级台阶的走法数而dp[n]正表示该值因此直接返回dp[n]。若n在初始范围内1~3则直接返回对应的初始化值无需进入递推循环避免越界访问。七、代码展示#include vector using namespace std; class Solution { public: int waysToStep(int n) { //处理边界情况 if (n 1) return 1; if (n 2) return 2; if (n 3) return 4; const int Mod 1e9 7;//模数 //1.创建dp表 vectorint dp(n 1); //3. 初始化 dp[1] 1, dp[2] 2, dp[3] 4; //2.状态转移方程 for (int i 4; i n; i) { //4. 填表顺序(从左到右) dp[i] ((dp[i - 3] dp[i - 2]) % Mod dp[i - 1]) % Mod; } //5. 返回值 return dp[n]; } };八、流程图