斐波那契(动规)

解题思路:

按照动规五部曲：

1. 定义动规数组和数组下标的含义：dp[i]表示：dp数组中第i个菲波那契数的值

   2.确定递推公式：
                                dp[i]=dp[i-1]+dp[i-2];}
     进而简化成：
                                sum=dp[1]+dp[0];
                                dp[0]=dp[1];
                                dp[1]=sum;
                          

 3.初始化dp数组(清楚递推公式后才清楚如何初始化数组)： dp[0]=0  ；dp[1]=1;

 4.确定遍历方式：从前往后遍历

 5.打印dp[]数组
注意事项:

参考代码:

package com.wyh.dynamic;

import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt();
       int [] dp=new int[2];
       //初始化dp数组
       dp[0]=0;
       dp[1]=1;
       //用于存储结果
       int sum=0;
       //递推公式
       if (n<2){
           System.out.println(1);
           return;
       }else {
           for (int i=2;i<=n;i++){
               sum=dp[1]+dp[0];
               dp[0]=dp[1];
               dp[1]=sum;
           }
           System.out.println(dp[1]);
       }
   }
}