算法学习-动态规划

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

适用情况

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。 无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
**子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

实例

求解的关键:第一步找到问题的“状态”, 第二步找到“状态转移方程”

示例一

一个序列有N个数:A[1],A[2],…,A[N],求出最长上升子序列的长度。 (讲DP基本都会讲到的一个问题LIS:longest increasing subsequence)

示例:5,3,4,8,6,7
前1个数的LIS长度d(1)=1(序列:5) 前2个数的LIS长度d(2)=1(序列:3;3前面没有比3小的)
前3个数的LIS长度d(3)=2(序列:3,4;4前面有个比它小的3,所以d(3)=d(2)+1) 前4个数的LIS长度d(4)=3(序列:3,4,8;8前面比它小的有3个数,所以 d(4)=max{d(1),d(2),d(3)}+1=3)

状态转移方程
dp[i]=max{dp[j]}+1,j=[0,i-1]且a[j]<a[i]
即为:到第i个元素的最长上升子序列=第0到i-1的元素的最长上升子序列+1
时间复杂度=O(n^2)

这个问题还有另一种更优化的解法,时间复杂度为O(nlog(n))
参考:https://leetcode.com/problems/longest-increasing-subsequence/

示例二

平面上有N*M个格子,每个格子中放着一定数量的苹果。你从左上角的格子开始走到右下角, 每一步只能向下走或是向右走,每次走到一个格子上就把格子里的苹果收集起来, 这样下去,你最多能收集到多少个苹果。

这个状态转移方程应该会更好理解
dp[i][j]=A[i][j]+max(dp[i+1][j], dp[i][j+1]),当然这里没有将边界问题考虑进来,实际编程中需要注意。

即为:从第i,j位置到走到左下角能收集的最大苹果数量=当前格子内苹果数量+向右走或向下走的两种方式的最大值