算法day28-动态规划（1）

目录

• 斐波那契数
  
• 爬楼梯
  
• 使用最小花费爬楼梯
  

 一、斐波那契数

https://leetcode.cn/problems/fibonacci-number/?envType=problem-list-v2&envId=8At1GmaZ

 　　这道斐波那契数列问题是动态规划的经典入门案例。我们通过定义 dp 表示第 i 个斐波那契数，利用状态转移方程 dp = dp[i - 1] + dp[i - 2] 从前向后推导，并以 dp[0]=0, dp[1]=1 为初始状态，最终得到 dp[n] 作为答案。该方法有效避免了递归的重复计算，时间复杂度为 O(n)，是理解动态规划“状态定义 + 递推关系 + 初始条件”三要素的绝佳练习。
[code]class Solution {    public int fib(int n) {        //1.确定dp数组的含义：dp表示第i个斐波那契数值        //2，确定递推公式：dp = dp[i-1] + dp[i-2];        //3.初始化        if(n==0 || n==1){            return n;        }        int[] dp = new int[n+1];        dp[0] = 0;        dp[1] = 1;        //4.确定遍历顺序：由前面推出后面        for(int i=2; i