对于初学者来说递推和递归的概念往往容易混淆。本文章将手把手教你如何区分递推和递归的区别以及详细讲解一道经典例题让你了解最基本的递推递推和递归的区别什么是递推用循环填表利用for循环与数组来实现例如for(int i3;iN;i) { dp[i]dp[i-1]dp[i-2]dp[i-3]; }不难发现dp[i]的状态取决于dp[i-1],dp[i-2],dp[i-3]。可见递推的核心在于由已知量推出未知量什么是递归函数的自我调用即函数在内部中调用自身例如int fib(int n) { if (n 0) return 0; // 边界1第0项是0 if (n 1) return 1; // 边界2第1项是1 return fib(n - 1) fib(n - 2); // 递归前两项之和 } int main() { int n 6; cout fib(6) endl; // 输出 8 return 0; }不难发现我们传入了实参6让fib函数实现自我调用本质区别递推从前往后推。从已知的起点边界条件开始顺着规律一直推到目标答案递归从后往前问。从目标答案开始往回拆拆到已知的起点边界条件就停止再把答案一层层传回来例题讲解例题出处详见洛谷P10250 [GESP样题 六级] 下楼梯题目描述顽皮的小明发现下楼梯时每步可以走 1 个台阶、2 个台阶或 3 个台阶。现在一共有 N 个台阶你能帮小明算算有多少种方案吗输入格式输入一行包含一个整数 N。输出格式输出一行一个整数表示答案。数据范围对全部的测试点保证 1≤N≤60。思路对于这题我们可以这样思考想象你站在楼梯下要上到第 4 级台阶N4每次可以迈 1、2 或 3 级你要上到第 4 级只看最后一步如果最后一步迈了 1 级那你前面必须已经站在 第 3 级 上如果最后一步迈了 2 级那你前面必须已经站在 第 2 级 上如果最后一步迈了 3 级那你前面必须已经站在 第 1 级 上所以到第4级的走法 到第3级的走法 到第2级的走法 到第1级的走法这个规律对任何一级台阶都成立要上到第 i 级只看最后一步最后一步迈1级 → 前面在 i-1 级最后一步迈2级 → 前面在 i-2 级最后一步迈3级 → 前面在 i-3 级所以f(i) f(i-1) f(i-2) f(i-3)最后一点定义初始量dp[0]1,到第0级阶梯只有1种走法原地站着dp[1]1,,到第1级阶梯只有1种走法dp[2]2,,到第2级阶梯只有2种走法分别走一步或直接走两步手动模拟阶梯数 i计算过程递推公式dp[i]走法总数0初始值原地不动11初始值只能走1步12 初始值11 或 223dp[2] dp[1] dp[0] 2 1 144dp[3] dp[2] dp[1] 4 2 175dp[4] dp[3] dp[2] 7 4 2136dp[5] dp[4] dp[3] 13 7 4247dp[6] dp[5] dp[4] 24 13 7448dp[7] dp[6] dp[5] 44 24 1381代码实现#include iostream using namespace std; int main() { int N; cinN; long long dp[65]; //多开5个防止数组越界 //定义初始量从前往后由已知量推未知量 dp[0]1; dp[1]1; dp[2]2; for(int i3;iN;i) { dp[i]dp[i-1]dp[i-2]dp[i-3]; } coutdp[N]; return 0; }