动态规划应用：解决楼梯攀爬问题——初探

动态规划简介&＃xff1a;

• 动态规划

  • 动态规划的核心思想&＃xff1a;就是将求解问题分解成多个相互交叠的子问题进行求解&＃xff0c;每次求解小型子问题的同时记录计算结果&＃xff08;相当于一个备忘录&＃xff09;&＃xff0c;在求解较大型子问题的时候会依赖于小型子问题的计算结果&＃xff0c;避免重复计算。
  • 子问题&＃xff1a;子问题的意思就是相对于求解问题来说仅仅是计算的规模变小了&＃xff0c;解决问题的目标和思路都没有改变。&＃xff08;例如&＃xff1a;二分查找每次将数组分为两部分&＃xff0c;每一部分的查找就可以看做是一个子问题&＃xff09;
  • 相互交叠的子问题&＃xff1a;相互交叠的意思就是大型子问题会包含小型子问题的求解。也就是说求解大型子问题的时候会用到小型子问题求解的计算结果。

• 动态规划三要素&＃xff1a;最优子结构&＃xff0c;边界&＃xff0c;状态转移函数

  • 最优子结构&＃xff1a;其实就是子问题的求解的结果一定是要最优的&＃xff0c;每个阶段的最优状态可以由之前的某个阶段的状态得到或者直接得到
  • 边界&＃xff1a;指最小子问题的解&＃xff0c;在代码中就是递归的出口或者是备忘录的初始值
  • 状态转移函数&＃xff1a;指从一个状态转移到另一个状态的具体模式&＃xff0c;其实也就是两个&＃xff08;多个&＃xff09;相邻子问题之间的关系

问题描述&＃xff1a;

• 假设小明要走一个n级的楼梯&＃xff0c;一步走一级或者一步走两级&＃xff0c;问他走到顶有多少种方法。
• 举个例子&＃xff0c;他可以每次走一步&＃xff0c;那么他走了10步&＃xff1b;他也可以一次走两步&＃xff0c;他走了5步&＃xff1b;解题的人要找到所有走的方案。

解题思路&＃xff1a;

• 假设 n &＃61; 10
• 如果我们从第一步开始看&＃xff0c;第一步可能走一级或者两级&＃xff0c;第二步也可能会走一级或者两级&＃xff0c;这样不断的去计算会显得非常复杂&＃xff0c;那么我们不妨从后往前看。
• 现在假设已经走到了最后一步&＃xff0c;小明只需要跨一步就可以走到第十级&＃xff0c;那么此时小明可能站在第八级的上面或者站在第九级的上面
• 那么如果我们已经知道走到第八级有X种走法&＃xff0c;走到第九级有Y种走法&＃xff0c;则走到第十级的走法就是X &＃43; Y
• 设F&＃xff08;n&＃xff09;为走到n级的走法数&＃xff0c;那么F&＃xff08;10&＃xff09; &＃61; F&＃xff08;8&＃xff09; &＃43; F&＃xff08;9&＃xff09;&＃xff0c;那么推广到一般的情况就是F&＃xff08;n&＃xff09;&＃61; F&＃xff08;n-1&＃xff09;&＃43; F&＃xff08;n -2&＃xff09;
• 此时动态规划的三要素就全部出现了&＃xff1a;
  • 状态转移方程&＃xff1a;F&＃xff08;n&＃xff09;&＃61; F&＃xff08;n-1&＃xff09;&＃43; F&＃xff08;n -2&＃xff09;
  • 边界就是最小子问题&＃xff1a;即F&＃xff08;1&＃xff09; &＃61; 1&＃xff0c; F&＃xff08;2&＃xff09; &＃61; 2
  • 最优子结构&＃xff1a;F&＃xff08;n-1&＃xff09;&＃xff0c; F&＃xff08;n -2&＃xff09;

注意&＃xff1a;这一题其实是非常简单的一道题目&＃xff0c;实际上并没有用到备忘录的设计&＃xff0c;但是主要的思想其实就是划分相互交叠的子问题&＃xff0c;记录计算结果&＃xff0c;进行状态转移

具体实现&＃xff1a;

public static int runSteps(int n){if(n < 0) return 0;if(n &＃61;&＃61; 1) return 1;if(n &＃61;&＃61; 2) return 2;return runSteps(n-1) &＃43; runSteps(n-2);}