LeetCode算法训练-动态规划

欢迎关注个人公众号：爱喝可可牛奶
LeetCode算法训练-动态规划

理论知识

动态规划当前状态是由前一个状态推导出来的，而贪心没有状态的转移
动态规划需要借助dp数组，可能是一维也可能是二维的

• 首先要明确dp数组是用来干什么的，下标对应什么
  
• 状态如何转移 ？ 也就是理清递推公式
  
• dp数组如何初始化
  
• 如何遍历
  
• 举个栗子模拟推导一遍
  

LeetCode 509. 斐波那契数

分析

F(n) = F(n - 1) + F(n - 2)，其中 n > 1
代码

[code]class Solution {    public int fib(int n) {        if (n