题目
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
思考
- 1、这道是动态规划的入门题目
- 2、简单的递推方程都给我们了
代码和注释
/**
标准的动态规划
1、dp下标的含义
2、确定递推公式
3、dp数组的初始化
4、确定遍历顺序（从前到后，从后到前）
5、log dp
*/
class Solution {
public int fib(int n) {
// 边界
if(n <= 1){
return n;
}
// 1、dp[i] 代表的是第n个数据
int[] dp = new int[n + 1];
// 2、确定递推公式(dp[n] = dp[n- 1] + dp[n-2])
// 3、初始化dp数组
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i -2];
}
return dp[n-1];
}
}
总结
- 动态规划五部曲
- 1、确定递推数组下标的意义
- 2、确定动态方程
- 3、初始状态
- 4、遍历顺序（前=》后/后=》前）
- 5、可尝试打印判断数组和我们想的是不是一样
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96120.html
