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

wikipedia

动态规划适用范围

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

动态规划问题分析步骤

  1. 确定状态
    研究最优策略的最后一步,将问题逐渐分解,转换为子问题。
  2. 转移方程
    根据子问题的定义得到转移方程.
  3. 初始条件和边界情况
    根据问题条件考虑初始条件和边界情况。
  4. 计算顺序
    利用之前的计算结果,逐渐推导得出答案。

动态规划题目举例

这里暂时列举几道动态规划的典型例题,之后如果有遇到值得记录的题目,会更新在这里。

题目一:买卖股票的最佳时机

题目链接

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

分析思路:这个题是一个比较简单的动态规划问题,我们可以想象下,求最后一天的最大股票收益,是不是等于求前一天的最大收益和今天的最大收益之间的最大值,同时我们很容易求出初始状态,即第一天/第二天的股票收益。

确定状态: 根据第一天/第二天的股票收益逐步计算出最后一天的股票收益。

转移方程: f(n) = max(f(n-1), prices(i) – phrasePrice) 其中 prices(i)为当天价格,phrasePrice为买入价格。

初始状态: 第一天股票收益: f(1) = 0, 第二天股票收益: f(2) = prices(2) – phrasePrice

参考代码:


题目二:最小路径和

题目地址

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

分析思路: 看题目最小XXX很容易想到动态规划,仔细看下最后的状态可以分解为多个子状态,动态规划无疑。

确定状态:mn的最小路径可以看成m-1n-1的最小路径,m-1n-1的到mn有两种可能,向下或者向右,由此我们可以得出转移方程。

转移方程: f(m,n)=min(f(m,n-1)+grid(m,n),f(m-1,n)+grid(m,n))

初始条件: m=0的时候,只能向右走,即f(m,n)=f(0,n-1)+grid(m,n);
n=0的时候,只能向下走,即f(m,n)=f(m-1,0)+grid(m,n);

计算顺序: 顺序计算到f(m,n)

参考代码:


题目三:最大自序和

题目地址

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

分析思路: 最值问题是明显的动态规划特征,仔细思考下可以发现,最后的最值可以使用之前的状态。

转移方程: f(n) = max(f(n -1) + nums(n), num(n)), 同时记录最大值max

初始条件: f(0) = num(0),即第一个元素的最大和是其本身。

计算顺序: 从f(0) 计算到 f(n)。

参考代码:


题目四:最长上升子序列

题目地址

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

分析思路: 求最长的上升子序列,假设这个问题为f(n), 我们可以看出f(n)和之前的状态有一定的关系,可以通过从第一个元素开始逐渐计算上升自序列,
到数组最后一个元素是即为最长的上升自序列。

转移方程:if nums(j) < nums(i) ; f(n) = max(f(n), f(j) + 1)

初始条件: f(0) = 1,每个f(n)初始值都可以假设为1,然后我们逐渐迭代计算。

计算顺序:从f(0)到f(n)

参考代码:


题目五:最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

分析思路:
这道题首先可以想到使用暴力搜索法求解,搜索出所有的回文字符串,然后比较长度即可,这个过程的时间复杂度是O(n^3)。
我们尝试使用动态规划推导这个问题,每个回文字符串有个特点,即两边相对中间是对称的,所以可以假设最终的结果是由最中间的字符串逐渐向两边推导的。

确定状态: 我们首先需要确定中间的字符串,然后逐渐向两边推导,比如找出 “d” ,然后逐渐推导出abcdcba。假设left, right是我们逐渐推导的变量,等到dp结束后,我们找出区间最大的left – right
,然后从原字符串截取即为最长回文子串。整个过程时间复杂度为O(n^2),空间复杂度为O(n^2)。

转移方程: 假设左边的坐标为left, 右边的坐标为right。 转移方程为:right-left=1时,f(left,right) = s(left) == s(right);right-left>1时, f(left, right) = s(left) == s(right) and f(left+1, right-1);

初始条件: 初始条件为 f[0][0] 到 f[s.length-1][s.length-1]都为true, 因为区间只有一个字符串的情况下,永远都算回文。

计算顺序: 从后往前进行计算,即 f(0, 0) -> f(1, 0) -> f(2, 1) -> f(2, 0) -> … -> f(s.length-1)(0)

代码实现:


好了,先举几道leetcode上的题为例,后面有经典的题我再补充到这里,欢迎大家留言,我们一起学习 🙂

2 对 “动态规划问题分析与解决”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注