题解 | #明明的随机数#

动态规划入门——求斐波那契数列第n个数

    public int fib(int n) {
        /*  1、dp数组及下标含义
            2、递推公式
            3、dp数组如何初始化
            4、遍历顺序
            5、打印dp数组(debug)*/
    
    //1、确定dp数组下标含义（状态转移）：dp[i]表示第i个斐波那契数为dp[i]
    int[] dp=new int[n+1];
    //2、递推公式:dp[i]=dp[i-1]+dp[i-2]
    //3、初始化
      if(n<=1){
        return n;
    }
    dp[0]=1;
    dp[1]=1;
    //4、遍历顺序：一维，从前向后遍历，保证dp[i]由dp[i-1]和dp[i-2]推出
    for(int i = 2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n-1];
    }
}