算法系列之动态规划
动态规划
简介
动态规划是一种实用的技巧,它可以用来解决一系列特定问题。它的思路很简单,如果你对某个给定的输入解决了一个问题,那么你可以保存已有信息,以避免重复计算,节约计算时间。
解决问题的方式
自顶向下 : 利用分支策略分解问题。如果你已经解决过当前子问题了,那么就返回已有信息。如果当前子问题没有计算过,那么就对它进行计算。这样的方法很易于思考、很直观。这被称作“记忆化”。
自底向上 : 首先分析问题,将问题分解为不同规模的问题,并决定它们的顺序,按顺序计算,直到解决给定规模的问题。这样的流程可以保证在解决较大的问题之前解决(它所依赖的)较小的问题。这种流程被称作“动态规划”。
动态规划的例子
最长上升子序列问题。给定S= {a[1] , a[2] , a[3], a[4], ............., a[n-1], a[n] }
,求出一个子序列,使得对于所有在这个子序列中所有满足j<i
的j
与i
,满足aj<ai
。首先我们要讨论以原序列的第i
个元素结尾的最长上升子序列dp[i]
。那么答案是整个 dp 序列的最大值。考虑dp[i]
,它的最后一个元素为a[i]
。枚举它的倒数第二个元素a[j]
,则a[j]<a[i]
成立。则dp[i]
就是所有这样的dp[j]
的最大值加上 1(最后一个元素)。这个算法具有*O(n^2)*的时间复杂度。
此算法的伪代码:
复制代码
这个算法的复杂度可以通过将数组换为其他数据结构来优化,来获得*O(n * log n)*的时间复杂度。
同样的思路可以求出有向无环图上的最大路径。
版权声明: 本文为 InfoQ 作者【坚果】的原创文章。
原文链接:【http://xie.infoq.cn/article/08c170cd1924f42e1e41cf1ae】。文章转载请联系作者。
评论