动态规划经典例题数列

动态规划（Dynamic Programming）是一种常用的算法思想，广泛应用于计算机科学中的优化问题。其基本思想是将问题分解成子问题求解，通过将子问题的解进行组合，得到原问题的解。动态规划的基础理论概念和应用方法在计算机科学中均有着广泛的应用。其中，数列相关的动态规划问题较为常见和典型。

一、数列及其性质

在动态规划问题中，常常涉及到数列及其性质。数列是有序的数集合，常用符号为{a1，a2……an}。

1.1 定义

数列的元素可以是任何数值。通常定义了一个数列后还要去定义它的长度，即用来表示数列中单独元素个数的变量。

1.2 常见性质

（1）递推规律：一般数列可以递归地定义，即每个后继项都是由其前面的项递推出来的；

（2）有界性：数列有最大值或最小值；

（3）周期性：数列元素值间有循环规律出现周期现象。

二、数列的动态规划经典例题

2.1 斐波那契数列

斐波那契数列是指数列1、1、2、3、5、8、13、21、34、……，其前两项均为1，其后每一项都是其前两项之和。可以看出斐波那契数列可以递归地定义，其状态转移方程为：

f[i] = f[i-1] + f[i-2]

即第i个数是第i-1个数和第i-2个数的和。

2.2 最长上升子序列

最长上升子序列问题是指：给定一个无序的整数数组，找到其中最长上升子序列的长度。其中，最长上升子序列指的是在原序列中子序列中数值严格上升的最长的序列。其状态转移方程为：

dp[i] = max{1,dp[j]+1}| i

即，dp[i]表示以第i个数结尾的最长上升子序列长度，dp[j]表示以第j个数结尾的最长上升子序列长度，当a[j]

2.3 最大子序和

最大子序和问题是指：给定一个整数序列，求其中最大连续子序列的和。其状态转移方程为：

dp[i] = max{dp[i-1]+a[i], a[i]}

即，dp[i]表示以第i个数结尾的最大子序和长度，当a[i]大于前面的子序和时可以将前面的子序和舍弃，只保留当前数，否则则加上前面的剩余数形成更大的子序和。

三、数列相关问题优化方法

3.1 记忆化搜索

记忆化搜索是一种动态规划思想，其基本思路是在递归时记录下每个状态所求解的值，每次求解函数执行前先查询记忆化数组，确定之前是否求解过该状态。如果已经求解过，则直接返回其值，否则计算出该状态的值并记录下来。从而避免了重复计算，提高运行速度。

3.2 滚动数组

滚动数组又称滚动优化，其基本思想是将动态规划中的状态数组，从一个二维数组压缩为一个一维数组。通过维护状态数组中的两个位置，即“上一阶段”和“当前阶段”，每次切换状态时实现原来二维数组的填表过程，从而大幅度减少内存空间开销，提高程序运行效率。

3.3 双指针

双指针优化是指在动态规划过程中，使用两个指针指向一个起点，然后从这个起点向两个方向延伸进行计算和比较，从而达到优化的目的。该方法在解决最长公共子序列和最长回文子串问题时，能够将时间复杂度优化到线性或常数级别，从而提高算法的效率。