写点什么

算法系列之动态规划

作者:坚果
  • 2022 年 6 月 18 日
  • 本文字数:672 字

    阅读完需:约 2 分钟

动态规划

简介

动态规划是一种实用的技巧,它可以用来解决一系列特定问题。它的思路很简单,如果你对某个给定的输入解决了一个问题,那么你可以保存已有信息,以避免重复计算,节约计算时间。

解决问题的方式

  1. 自顶向下 : 利用分支策略分解问题。如果你已经解决过当前子问题了,那么就返回已有信息。如果当前子问题没有计算过,那么就对它进行计算。这样的方法很易于思考、很直观。这被称作“记忆化”。

  2. 自底向上 : 首先分析问题,将问题分解为不同规模的问题,并决定它们的顺序,按顺序计算,直到解决给定规模的问题。这样的流程可以保证在解决较大的问题之前解决(它所依赖的)较小的问题。这种流程被称作“动态规划”。

动态规划的例子

最长上升子序列问题。给定S= {a[1] , a[2] , a[3], a[4], ............., a[n-1], a[n] },求出一个子序列,使得对于所有在这个子序列中所有满足j<iji,满足aj<ai。首先我们要讨论以原序列的第i个元素结尾的最长上升子序列dp[i]。那么答案是整个 dp 序列的最大值。考虑dp[i],它的最后一个元素为a[i]。枚举它的倒数第二个元素a[j],则a[j]<a[i]成立。则dp[i]就是所有这样的dp[j]的最大值加上 1(最后一个元素)。这个算法具有*O(n^2)*的时间复杂度。


此算法的伪代码:


for i=0 to n-1    dp[i]=0    for j=0 to i-1        if (a[i] >  a[j] and dp[i]<dp[j])            LS[i] = LS[j]    dp[i]=dp[i]+1for i=0 to n-1    if (largest < dp[i])        largest = dp[i]
复制代码


这个算法的复杂度可以通过将数组换为其他数据结构来优化,来获得*O(n * log n)*的时间复杂度。


同样的思路可以求出有向无环图上的最大路径。

发布于: 刚刚阅读数: 3
用户头像

坚果

关注

此间若无火炬,我便是唯一的光 2020.10.25 加入

公众号:“大前端之旅”,华为云享专家,InfoQ签约作者,51CTO博客首席体验官,专注于大前端技术的分享,包括Flutter,小程序,安卓,VUE,JavaScript。

评论

发布
暂无评论
算法系列之动态规划_6月月更_坚果_InfoQ写作社区