动态规划-斐波那契数列

动态规划（Dynamic Programming, DP）是一种在数学、盘算机科学和经济学中利用的，通过把原标题分解为相对简朴的子标题的方式求解复杂标题的方法。动态规划通常用于求解最优化标题，如最短路径标题、背包标题、项目调治标题等。其核心头脑是将待求解的标题分解成多少个简朴的子标题，先求解子标题，然后从这些子标题的解得到原标题的解。动态规划会生存已办理的子标题的答案，从而克制重复盘算，进步算法服从。
动态规划的根本步调

  

• 界说状态：
  起首，须要确定标题的状态体现，即怎样形貌一个子标题的解。状态通常是一个或多个变量的组合，用于体现子标题的当进步度或条件。
    
  
• 创建状态转移方程：
  状态转移方程形貌了怎样从较小的子标题的解推导出较大子标题的解。它界说了怎样根据前一个或多个状态来盘算当前状态的值。
    
  
• 初始化界限条件：
  确定状态转移方程的界限条件，即最小的子标题（通常是标题的出发点或最简朴的环境）的解。
    
  
• 盘算次序：
  根据标题的性子，确定盘算状态的次序。这通常是从最简朴的子标题开始，徐徐盘算更复杂的子标题，直到到达原标题的解。
    
  
• 优化（可选）：
  在现实应用中，大概须要进一步优化动态规划算法，如通过影象化搜索淘汰重复盘算，大概利用数据布局（如线段树、树状数组等）来加快状态转移的盘算。
  
  

示例1：斐波那契数列-爬楼梯

假设你正在爬楼梯。须要 n 阶你才气到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种差异的方法可以爬到楼顶呢？
这是一个非常经典的动态规划标题，其

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金