leetcode总结无止境系列之动态规划及比较

####动态规划: 1、基本思想:将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

2、步骤设计:

  • 分析最优解的性质,并刻画其结构特征。
  • 递归的定义最优解。
  • 以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
  • 根据计算最优值时得到的信息,构造问题的最优解

3、应用题型:最短路径,最长公共子序列,最大价值

tip1:算法导论中有对动态规划四个典型例题的详细剖析,这里给出一个读书笔记传送门:动态规划

tip2:TopCoder上的一篇文章:Dynamic Programming: From novice to advanced

####算法间的关联与不同

1、分治法与动态规划

分治法所能解决的问题一般具有以下几个特征

(1)该问题的规模缩小到一定程度就可以容易地解决。

(2)该问题可以分为若干个较小规模的相似的问题,即该问题具有最优子结构性质。

(3)利用该问题分解出的子问题的解可以合并为该问题的解。

(4)该问题所分解出的各个子问题是相互独立的且子问题即之间不包含公共的子问题

上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是分治法应用的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心算法或动态规划算法;第四条特征涉及到分治法的效率,如果各个子问题不是独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。这类问题虽然可以用分治法解决,但用动态规划算法解决效率更高。

当问题满足第一、二、三条,而不满足第四条时,一般可以用动态规划法解决。可以说,动态规划法的实质是,分治算法思想+解决子问题冗余情况

2、贪心算法与动态规划算法

多阶段逐步解决问题的策略就是按一定顺序或一定的策略逐步解决问题的方法。分解的算法策略也是多阶段逐步解决问题策略的一种表现形式主要是通过对问题逐步分解然后又逐步合并解决问题的。

贪心算法每一步都根据策略得到一个结果,并传递到下一步,自顶向下,一步一步地做出贪心决策。

动态规划算法的每一步决策给出的不是唯一结果,而是一组中间结果,而且这些结果在以后各步可能得到多次引用,只是每走一步使问题的规模逐步缩小,最终得到问题的一个结果。

适用条件

贪心算法:(1)贪心选择性质(2)最优子结构

动态规划:(1)最优化原理(2)无后效性(3)有重叠子问题

应用题型

贪心:最小生成树、最短路径、数据压缩-哈夫曼编码

分治:二分搜索、大整数乘法、归并排序、快排、最接近点对问题、汉诺塔

动态规划:装配线、矩阵乘法、最长公共子序列、构造最优二叉查找树


leetcode 上相关题目汇总

1.Longest Palindromic Substring

2.Regular Expression Matching

3.Container With Most Water

4.Maximum Subarray

5.Minimum Path Sum

6.Minimum Window Substring

7.Maximal Rectangle

8.Unique Paths

9.Unique Paths II

10.Best Time to Buy and Sell Stock

11.Best Time to Buy and Sell StockII

12.Best Time to Buy and Sell StockIII

crystal /
Published under (CC) BY-NC-SA in categories 面试  tagged with 算法  leetcode