动态规划 0（斐波那切数列 leetcode 509）

手机软件开发 · 2024-9-20 02:32:31

头脑

动态规划的核心头脑是分治，将复杂题目转换成子题目，通过子题目的迭代渐渐迫近真实题目。
这个过程拆解为：
（1）根据题目探求状态
（2）定义 dp 数组
（3）明确怎样选择，即状态转移方程
（4）明确 base case 和初始值
实例

斐波那切数列 leetcode 509
一个数列由 0 和 1 开始，背面每一项数字都是前面两项数字的和。
状态

这是一个简朴示例，题目中没有任何干扰信息，只有数字的值，状态也就是数字的值。
dp 数组

状态是数字的值，dp 数组存储状态即可。
这里要留意的是 dp 数组下标和数字的项的关系。一种方式是二者同步，下标是从 0 开始的，数字的项定义为输入的 n 值，n >= 0。
[0, 1] 是 dp 数组的前两项，代表的含义是输入值 n=0 和 n=1。
状态转移方程

这个题目中方程已经在标题中阐明，每一项是前两项之和，即 F(n) = F(n-1) + F(n-2) n>1.
也就是说当输入 n=3 时，F(2) = F(1) + F(0) = 1 + 0 = 1
初始值

界限条件是 F(1) = 1, F(0) = 0
编码

动态规划 0（斐波那切数列 leetcode 509）

所属分类: 问答交流

新帖推荐: 30日

推荐作品