11《算法入门教程》动态规划介

Tips: 这里说到的动态规划应用于子题目相互重叠的情况，是指原题目差异的子题目之间具有雷同的更小的子子题目，他们的求解过程和效果完全一样。

• 最优子布局： 利用动态规划算法求解题目的第一步就是须要描画题目最优解的布局，而且如果一个题目的最优解包罗其子题目的最优解，则此题目具备最优子布局的性子。因此，判定某个题目是否适适用动态规划算法，须要判定该题目是否具有最优子布局。
  

Tips: 最优子布局的定义重要是在于当前题目的最优解可以从子题目的最优解得出，当子题目满意最优解之后，才可以通过子题目的最优解得到原题目的最优解。

• 重叠子题目： 适适用动态规划算法去求解的最优化题目应该具备的第二个性子是题目的子题目空间必须富足” 小 “，也就是说原题目递归求解时会重复雷同的子题目，而不是不绝天生新的子题目。如果原题目的递归算法反复求解雷同的子题目，我们就称该最优化题目具有重叠子题目。
  

Tips: 在这里，我们须要留意是，与实用动态规划算法去求解的题目具备重叠子题目性子相反，前面我们先容的分治算法递归解决题目时，题目的子题目都是互不影响，相互独立的，这个也是我们在选用动态规划算法照旧分治法解决题目时的一个判定条件。

情况 1：输入 n=1；输出为 1
表明 1：有一种情况可以爬上楼顶， 爬 1 步，记为 1

情况 2：输入 n=2；输出为 2
表明 2：有两种情况可以爬上楼顶，分别为连续两次爬一阶楼梯和一次爬两阶楼梯，记为 1+1，2

情况 3：输入 n=3；输出为 3
表明 3：有三种情况可以爬上楼顶，如情况 1 和 2 形貌一样，记为 1+1+1,2+1,1+2

Tips: 在这里，我们可以发现爬楼梯题目满意第 3 节我们定义的动态规划算法须要具备的两种性子，此中的最优子布局就是：爬上 n 阶楼梯的最多方法数包罗爬上第 n-1 楼梯和第 n-2 阶楼梯的最多方法数；重叠子题目：须要反复的盘算爬各阶楼梯的最多方法数。

• 上 1 阶台阶：有 1 钟方法；
  
• 上 2 阶台阶：有 1+1 和 2 两种方法；
  
• 上 3 阶台阶：到达第 3 阶的方法总数是到达第 1 阶和第 2 阶方法的总和；
  
• 上 n 阶台阶：到达第 n 阶的方法总数就是到第 (n-1) 阶和第 (n-2) 阶的方法数之和。