| 走台阶问题（递归方法+动态规划） | 您所在的位置：网站首页 › 阶梯法技术图解 › 走台阶问题（递归方法+动态规划） |
走台阶问题（递归方法+动态规划）
|
参考链接：https://time.geekbang.org/column/article/41440 基本的走台阶问题问题描述：假设有n个台阶，每跨一步只能上1阶或者2阶台阶。求总共有多少种走法 思路1：假设n阶台阶有f(n)种走法，可以通过递归的方式进行求解。因为一步可以上1阶或者2阶台阶，那如果先上1个台阶则只需求出剩下的n-1个台阶的走法，如果先上2个台阶则只需求出剩下的n-2个台阶的走法，所以求n个台阶的走法变为求n-1和n-2个台阶的走法，则有f(n) = f(n - 1) + f(n - 2)(其中n > 2)。 基于以上思路，代码实现如下： /* * @brief 利用递归解决该问题 * * @method: SolveStep * @access: public * @param: size_t nStair * @Return: size_t * @author: RF_LYF * @since: 2019/4/23 9:57 */ DWORD SolveStep(size_t nStair) { if(nStair 0) return nStair; else return SolveStep(nStair - 1) + SolveStep(nStair -2); }该方法，当台阶的个数超过一定值得时候，求解速度很慢。 思路2：上面方法求解速度慢主要原因是存在好多重复计算。如下图所示：
由图可知在求解f(6)时f(3)被计算了3次，f(4)被被计算了2次，这种重复计算在上面的实现方式中出现很多，因此我们为了避免重复计算，可以将已经计算过的结果保存下来，从而减少计算次数，提高计算效率 。 基于以上分析，代码实现如下： /** * @brief 采用自顶向下的动态规划方式进行求解 * * @method: SolveStepOpti * @access: public * @param: size_t nStair * @param: int * Counter * @Return: ULONG * @author: RF_LYF * @since: 2019/4/23 10:33 */ DWORD SolveStepOpti(size_t nStair, int *Counter) { if(0 !=Counter[nStair]) return Counter[nStair]; if(nStair 0 && nStair < 3) { return Counter[nStair] = nStair; } else { Counter[nStair] = SolveStepOpti(nStair - 1, Counter) + SolveStepOpti(nStair - 2, Counter); return Counter[nStair]; } }该方法的计算速度有了明显的提升。 思路3：利用循环的方式，完成该问题，采用自底向上的动态规划 /** * @brief 利用循环求解问题，自底向上的动态规划求解问题 * * @method: SolveStepOpti2 * @access: public * @param: size_t nStair * @Return: DWORD * @author: RF_LYF * @since: 2019/4/23 10:52 */ DWORD SolveStepOpti2(size_t nStair) { if(nStair |
【本文地址】
公司简介
联系我们