代码随想录算法训练营第三十八天|509. 斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯

509. 斐波那契数

public class Solution {
    public int Fib(int n) {
         if (n < 2)
         {
            return n;
         }
        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

首先分析状态转移方程，斐波那契数是由前面两个数加起来组成当前数，所以Dp[i]=Dp[i-1]+Dp[i-2],如果N小于2，则直接返回N，因为第一个数是0，第二个数1，所以Dp[0]=0,Dp[1]=1,所以结合状态方程最终返回出Dp[n]的值。

70.爬楼梯

public class Solution {
    public int ClimbStairs(int n) {
        if(n<=2)
        {
            return n;
        }
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

首先分析状态转移方程，爬楼梯一问题终点是由前面两台阶的组合加起来组成的，所以Dp[i]=Dp[i-1]+Dp[i-2],如果N小于2直接返回N，第一个阶梯只有一种方法，第二阶楼梯有两种方法分别是从起点一步一步过来，或者起点直接过来两种方法，所以Dp[1]=1,Dp[2]=2，同理最终返回Dp[n]的值。

746.使用最小花费爬楼梯

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int sum=0;
        int []dp=new int[cost.Length+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<dp.Length;i++)
        {
            dp[i]=Math.Min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[dp.Length-1];
    }
}

首先分析状态转移方程，爬楼梯一问题终点是由前面两台阶的组合加起来组成的所以是Dp[i-1]+Cost[i-1]和Dp[i-2]+Cost[i-2],但由于是开销最小，所以每次选这前两个方案中最小的作为开销使用，即Dp[i]=Math.Min(Dp[i-1]+Cost[i-1],Dp[i-2]+Cost[i-2]),最终Dp的最后一个值。