动态规划

Reference

https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

Intro

动态规划

定义

把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

适用情况

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

解题方法

  1. first step: Characterize the structure of an optimal solution
  2. second step: Recursively define the value of an optimal solution
  3. third step: Compute the value of an optimal solution
  4. At last:Construct an optimal solution from computed information

一般优化思路

  1. 写出状态转移方程
  2. 分析冗余, 去除冗余

实例

背包问题(Knapsack)

from “背包九讲”

01背包问题

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i] ,价值是 w[i] 。求解将哪些物
品装入背包可使价值总和最大。

用子问题定义状态:即 f[i][v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。
则其状态转移方程便是:

伪代码:

1
2
3
4
for i ← 1 to N
do bound ← max{V − sumw[i..n], c[i]}
do for v ← V to bound
do f[v]=max{f[v],f[v-c[i]]+w[i]};
  • 在每次主循环中我们以 v=V..0 的顺序推 f[v] ,这样才能保证推 f[v] 时 f[v-c[i]] 保存的是状态 f[i-1][v-c[i]] 的值。
  • 常数优化: 第二层循环的下限为max{V − sumw[i..n], c[i]}, 第二个分量容易理解, 但第一个是因为由于只需要最后 f[v] 的值,倒推前一个物品,其实只要知道 f[v-c[n]] 即可。以此类推,对第 j 个背包,其实只需要知道到 $\sum_j^n f [v − c[i]]$ 即可
  • 初始化的细节问题:
    • 要求恰好装满背包: 那么在初始化时除了 f[0] 为 0 其它 f[1..V] 均设为 −∞ ,这样就可以保证最终得到的 f[N] 是一种恰好装满背包的最优解。
    • 不需要恰好:如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 f[0..V] 全部设为 0 。

分析

时间复杂度为$\mathcal{\Theta}(NV)$, 空间复杂度为$\Theta(V)$

完全背包问题

有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。第 i 种物品的费用是 c[i] ,
价值是 w[i] 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最
大。

状态转移方程

伪代码:

1
2
3
for i ← 1 to N
for v ← cost to V
do f [v] = max{f [v], f [v − k * c[i]] + k * w[i]}

分析

时间复杂度为$\Theta(V\times V\sum \frac{V}{c[i]})$, 空间复杂度为$\Theta(V)$

装配线调度问题

img

A manufacturing problem to find the fastest way through a factory. There are two assembly lines, each withn stations; the jth station on line i is denotedSi,jand the assembly time at that station isai,j. An automobile chassis enters the factory, and goes onto linei (where i = 1 or 2), taking ei time. After going through thejth station on a line, the chassis goes on to the (j + 1)st station on either line. There is no transfer cost if it stays on the same line, but it takes time ti,j to transfer to the other line after stationSi,j. After exiting thenth station on a line, it takesxi time for the completed auto to exit the factory. The problem is to determine which stations to choose from line 1 and which to choose from line 2 in order to minimize the total time through the factory for one auto.

最大连续子序列

之和

https://www.cnblogs.com/AlvinZH/p/6795647.html

问题描述:给定一个序列(整数或浮点数),求出其中连续的子序列和最大的那一个。

例:序列{-10 1 2 3 4 -5 -23 3 7 -21}

其最大的连续子序列为{1 2 3 4}或{3 7},最大和为10.

暴力求解

最最普通的方法,效率十分低,一般不会用到,这里简单介绍。直接两个for循环枚举子序列的首尾,再来一个for循环计算首尾之间的序列和,计算所有的序列和,找到最大值。

时间复杂度:O(n^3)

预处理暴力求解

第一种方法为什么这么慢,原因之一是每次都要计算首尾之间的序列和。基于这个考虑,我们可以对数据进行预先处理:读入数据时使用一个数组SUM[i]来记录前i项数据之和。用这种方法,只需要两个for循环枚举子序列的首尾,利用SUM数组计算子序列和,找到最大值。

时间复杂度:O(n^2)

分治法求解

把序列分成左右两部分,一般对半分,数量不等也没关系。最大子序列和的位置存在三种情况

  • 完全在左半部分
  • 完全在右半部分
  • 跨越左右两部分

分别求出左半部分的最大子序列和、右半部分的最大子序列和、以及跨越左右两部分的最大子序列和,三者中的最大者就是要求的。

如何求三部分的最大子序列和呢?

左半部分的最大子序列和,可把左半部分作为新的输入序列通过该算法递归求出。右半部分的最大子序列和同理。

接下来就是求解跨越左右两部分的最大子序列和,也就是求出包含左半部分中最右边元素的子序列的最大和,和包含右半部分中最左边元素的子序列的最大和,将两者相加即为跨越左右两个部分的最大子序列和。具体见如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
> //分治算法 
> int a[999999];
>
> int MAxSubSum(int left,int right)
> {
> int sum=0;
> if(left==right)//基本情况:只有一个元素
> sum=a[left]>0?a[left]:0;
> else
> {
> int center=(left+right)/2;
> int leftsum=MaxSubSum(left,center);//左半部分
> int rightsum=MAxSubSum(center+1,right);//右半部分
>
> //求包含左半部分最右元素的最大和
> int s1=0;
> int lefts=0;
> for(int i=center;i>=left;i--)
> {
> lefts+=a[i];
> if(lefts>s1) s1=lefts;
> }
>
> //求包含右半部分最左元素的最大和
> int s2=0;
> int rights=0;
> for(int i=center+;i<=right;i++)
> {
> rights+=a[i];
> if(rights>s2) s2=rights;
> }
>
> //取三者最大值
> sum=s1+s2;
> if(sum<leftsum) sum=leftsum;
> if(sum<rightsum) sum=rightsum;
> }
> return sum;
> }
>

>

时间复杂度:O(nlgn)

状态转移方程

sum[i] = max{sum[i-1]+a[i],a[i]}.

(sum[i]记录以a[i]为子序列末端的最大序子列连续和)

其实完全可以不用开数组,累计sum直到sum + a < a,把sum赋值为a,更新最大值就行了。

1
2
3
4
5
6
7
8
9
10
11
12
//动态规划算法
int MaxSum(int n)
{
int sum=0,b=0;
for(int i=0;i<n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}

时间复杂度:O(n)

不超过m之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxSumSubSeqLessK(vector<int>& sums, int k) {
// Find the max subarray no more than K
set<int> accuSet;
accuSet.insert(0);

int curSum = 0, curMax = INT_MIN;

for (int sum : sums) {
curSum += sum;
set<int>::iterator it = accuSet.lower_bound(curSum - k);
if (it != accuSet.end()) curMax = std::max(curMax, curSum - *it);
accuSet.insert(curSum);
}

return curMax;
}

之积

from https://leetcode.com/problems/maximum-product-subarray/description/

最大乘积本质上与最大和是一样的,但是由于存在负数,所以需要同时记录最小值和最大值.

每次都更新maxend,minend.

那么状态转移方程为:

1
2
maxend = max(max(maxend*data[i] , minend*data[i]) , data[i]);
minend = min(min(maxend*data[i] , minend*data[i]) , data[i]);

初始状态为 maxend = minend = data[0];

为什么非要比较data[i]而不是和之前的maxend or minend 比较呢?因为它是一个连续的串,所以必须每一个部分都要乘进来,如果是一个不连续的最大乘积,那么是与之前的maxend or minend作比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
/**
* @param nums: a vector of integers
* @return: an integer
*/
int maxProduct(vector<int>& nums) {
// write your code here
int maxend= nums[0];
int minend= nums[0];
int ret = nums[0];
for(int i=1;i<nums.size();i++)
{
int tempPosMax = maxend;
int tempNegMax = minend;
maxend= max(nums[i],max(nums[i]*tempPosMax,nums[i]*tempNegMax));
minend= min(nums[i],min(nums[i]*tempPosMax,nums[i]*tempNegMax));
ret = max(ret,maxend);
}
return ret;
}
}

矩阵链相乘(matrix-chain multiplication)

from: https://blog.csdn.net/qq_24145735/article/details/51089697

给定一串矩阵 $A1,A2…An$,计算矩阵的值:$A_1A_2A_3..A_n$。对于这串矩阵序列,不同的加括号方式,会导致截然不同的计算量。我们需要做的就是计算出如何加括号,达到最少计算量。

使用动态规划求解

  1. first step: Characterize the structure of an optimal solution
    数学定义:$A_{i..j}$ : 矩阵乘—–$A_iA_{i+1}··A_j$
    存在$k$ 使得$i \le k \lt j$
    把$A_{i··j}$ 划分为 $A_{i··k}$ 和$A_{(k+1)··j}$
    假设此时的k正好为最优划分,使得$A_{i··j}$矩阵相乘的规模最小
    反证: 如果此时k对原来矩阵序列的划分不是最优的,则肯定存在另一个k,使得划分为最优:与假设矛盾。

  2. second step: Recursively define the value of an optimal solution现在我们定义递归求解这个子问题:$A_{i··j}$ 为: 矩阵$A_iA_{i+1}··A_j (1 \le i \le j \le n)$
    数学定义:$M[i,j] = A_{i··j}$ 的最小矩阵乘规模
    定义数组P,使得矩阵A_i的维度为 = $p[i-1] * p[i]$。$p[i-1]$代表矩阵的行, $p[i]$代表矩阵的列)
    如图1
    这里写图片描述
    A_3 的行下标为 p[2]=15 列下标为p[3]=5当$i = j : A_{i··j} = A_i,$单个矩阵,所以M[i,j]=0
    当$i < j : A_{i··j}$可分为$A_{i··k}$的矩阵乘规模数加上$A_{k+1}··A_j$的矩阵乘规模数,再加上两个分矩阵的相乘规模数
    数学表达式为:$M[i,j] = M[i,k] + M[k+1,j] + p_{i-1}p_kp_j$
    重点理解$p_{i-1}p_kp_j$表达的意思:现在$M[i,k]$可理解为最终行下标为i,列下表为k的矩阵;$M[k+1,j]$可理解为最终行下标为k+1,列下表为j的矩阵;再把这两个矩阵相乘,也就是等同于两个矩阵相乘的规模数,再结合图一,得出结果——$p_{i-1}p_kp_j$

  3. third step: Compute the value of an optimal solution

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    matrix(p,i,j) {
    if i == j
    m[i,j] = 0
    retrun m[i,j]
    m[i,j] = 999999999999
    for k = i to j - 1
    temp = matrix(p,i,k) + matrix(p,k+1,j) + p[i-1]p[k]p[j]
    if temp < m[i,j]
    m[i,j] = temp
    return m[i,j]
    }
  4. At last:Construct an optimal solution from computed information

    1
    2
    3
    4
    5
    6
    for i = 1 to n do C(i,j) = 0
    for s = 1 do n - 1 do
    for i = 1 to n - s do
    j = i + s
    C(i, j) = min{i <= k <= j} {C(i,k) + C(k+1,j) + m(i-1) * m(k) * m(j)}
    return C(1,n)

编辑距离(Edit Distance)

https://blog.csdn.net/baodream/article/details/80417695

字符串的编辑距离,又称为Levenshtein距离,由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符操作包括:

  • 删除一个字符 a) Insert a character

  • 插入一个字符 b) Delete a character

  • 修改一个字符 c) Replace a character

例如对于字符串”if”和”iff”,可以通过插入一个’f’或者删除一个’f’来达到目的。

一般来说,两个字符串的编辑距离越小,则它们越相似。如果两个字符串相等,则它们的编辑距离(为了方便,本文后续出现的“距离”,如果没有特别说明,则默认为“编辑距离”)为0(不需要任何操作)。不难分析出,两个字符串的编辑距离肯定不超过它们的最大长度(可以通过先把短串的每一位都修改成长串对应位置的字符,然后插入长串中的剩下字符)。

问题分析:

考虑A串的第i个字符和B串的第j个字符。这个时候不考虑A的前i-1字符和B串的第j-1个字符。如果A串的第i个字符和B串的第j个字符相等,即A[i]=B[j],则只需要计算A[i+1…lenA]和B[j+1…lenB]之间的距离即可。如果不相等,则:

  • 修改A串的第i个字符成B串的第j个字符,之后仅需要计算A[i+1…lenA]和B[j+1…lenB]的距离即可;
  • 删除A串的第i个字符,之后仅需要计算A[i+1…lenA]和B[j…lenB]的距离即可;
  • 把B串的第j个字符插入到A串的第i个字符之前,之后仅需要计算A[i…lenA]和B[j+1…lenB]的距离即可。

    写到这里,自然会想到用递归求解或者动态规划求解,由于用递归会产生很多重复解,所以用动态规划。

状态转移方程:

伪代码:

1
2
3
4
5
6
7
8
for i = 0 to m do
edit[i][0] = i
for j = 1 to n do
edit[0][j] = j
for i = 1 to m do
for j = 1 to n do
flag = (A[i]==B[j])
edit[i][j]=min(edit[i-1][j]+1,edit[i][j-1]+1,edit[i-1][j-1]+flag)

分析:

时间复杂度$\Theta (m\cdot n)$

Shortest reliable paths & Floyd-Warshall algorithm

利用floyd算法求出的每k步是各点对间经过k条边的最短路径

伪代码:

1
2
3
4
for k = i to n do
for i = 1 to n do
for j = 1 to n do
dist(i,j,k)=min{dist(i,j,k-1),dist(i,k,k-1)+dist(k,j,k-1)}

分析:

时间复杂度$\Theta(n^3)$

旅行商问题(Travel Salesman Problem)

from https://www.jianshu.com/p/478f6b1fe60f

TSP(Traveling Salesman Problem)即旅行商问题,是数学领域中著名问题之一。这个问题是这样的:假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。TSP是一个典型的组合优化问题,且是一个NP完全难题,关于NP的这个概念本文就不做详细介绍了,但简单的说就是:TSP问题目前尚不能找到一个多项式时间复杂度的算法来求解。

子问题:

代码:

C({1,},1) = 0
for s = 2 to n do
for all subsets S $\in$ {1, … , n} of size s and containing 1 do
C(S, 1) = $\infty$
for all j $\in$ S and j $\neq$ 1 do
$C(S,j)=\min_{i\in S:i\neq j}C(S \setminus \{j\},i )+d_{ij}$

最长公共子序列(Longest Common Subsequence)

状态转移方程:

子集和问题(subset problem)

https://blog.csdn.net/a130737/article/details/44242047

给定一个包含N个非负数的set, 并且给定K, 从集合中找出一组元素子集, 使得这组子集的各个元素相加起来和是K。

创建一个2D的boolean table subset[i][j]。 然后自底向上的方式(所以没有递归)填充这个二维布尔数组。 如果存在一个子集合set[0..j-1],, 使得这个子集合的和等与i, 我们就记录subset[i][j]为true, 否则填充为false。 最后我们只需要返回subset[sum][n]即可。

状态转移方程:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// A Dynamic Programming solution for subset sum problem
#include <cstdio>

// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum) {
// The value of subset[i][j] will be true if there is a subset of set[0..j-1]
// with sum equal to i
bool subset[sum+1][n+1];

// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;

// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;

// Fill the subset table in botton up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
//
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
}
}


return subset[sum][n];
}

// Driver program to test above function
int main()
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}

路径搜索

都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:

1536141093604

为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)

这个题有很大的细节问题,就是在处理时间的时候,如果你选择从上往下,还要注意范围的变化,最后还要在可以行走的范围里寻找最大值,细节问题特别难处理。

但是如果从后往前推就会很容易,因为在0时刻人只会在5这个地方,所以用倒着的递归简单(这么厉害的想法当然不是我想的了,我借鉴的大神的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>

using namespace std;

int a[100002][11];
int f[100002][11];

int max3(int x,int y,int z)
{
if(x>=y && x>=z)return x;
else if(y>=x && y>=z)return y;
else return z;
}
int max2(int x,int y)
{
if(x>y)return x;
else return y;
}

int main()
{
int n, i, j, t, x, mt;
while (1) {
scanf("%d", &n);
mt = -1;
if (n == 0) break;

memset(a, 0, sizeof(a));
memset(f, 0, sizeof(f));

for (i = 0; i < n; ++i) {
scanf("%d %d", &x, &t);
if (mt < t) mt = t;
a[t][x]++;
}

for (i = mt; i >= 0; --i) {
for (j = 0; j <= 10; ++j) {
if (j >= 0 && j <= 9) f[i][j] = max3(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+a[i][j];
else if(j==0)f[i][j]=max2(f[i+1][j],f[i+1][j+1])+a[i][j];
else if(j==10)f[i][j]=max2(f[i+1][j-1],f[i+1][j])+a[i][j];

}
}

cout << f[0][5] << endl;
}
}

最长有效括号

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
4
> Input: "(()"
> Output: 2
> Explanation: The longest valid parentheses substring is "()"
>

>

Example 2:

1
2
3
4
> Input: ")()())"
> Output: 4
> Explanation: The longest valid parentheses substring is "()()"
>

所以此种做法的难度在于如何判断两个有效括号子串是否直接相邻,若直接相邻,则最长有效括号子串需要将这两个相邻的子串包含进来,并且左右边界需往外扩展,如上例中,下标2和下标21所处位置的字符其实也是在最长有效括号子串中的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
解题思路:

1.需有一个变量start记录有效括号子串的起始下标,max表示最长有效括号子串长度,初始值均为0

2.遍历给字符串中的所有字符

2.1若当前字符s[index]为左括号'(',将当前字符下标index入栈(下标稍后有其他用处),处理下一字符

2.2若当前字符s[index]为右括号')',判断当前栈是否为空

2.2.1若栈为空,则start = index + 1,处理下一字符(当前字符右括号下标不入栈)

2.2.2若栈不为空,则出栈(由于仅左括号入栈,则出栈元素对应的字符一定为左括号, 可与当前字符右括号配对),判断栈是否为空

2.2.2.1若栈为空,则max = max(max, index-start+1)

2.2.2.2若栈不为空,则max = max(max, index-栈顶元素值)

动态规划

需用到辅助数组d[s.length()],表示从当前字符开始,到字符串结尾的最长有效括号子串长度(当前字符需为有效括号子串的第一个字符)

解题思路:从字符串结尾往前处理,求辅助数组d[]

当前字符下标为index,若当前字符为左括号’(‘,判断index+1+d[index+1]位置的字符是否为右括号’)’,若为右括号,则d[index] = d[index+1]+2,并且判断index+1+d[index+1]+1位置的元素是否存在,若存在,则d[index] += d[index+1+d[index+1]+1](解决上述两个有效括号子串直接相邻的情况)

1541583942613

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int longestValidParentheses(string str) {
int ans = 0;
vector<int> dp(str.size(), 0);
for (int i = str.size() - 2; i >= 0; --i) {
if (str[i] == '(' && str[dp[i + 1] + i + 1] == ')') {
dp[i] = dp[i + 1] + 2;
if (i + 1 + dp[i + 1] + 1 < str.size()) {
dp[i] += dp[i + 1 + dp[i + 1] + 1];
}
}
ans = ans > dp[i] ? ans : dp[i];
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
int longestValidParentheses(string s) {
if(s.length() <= 1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')' && i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
curMax = max(longest[i],curMax);
}
}
return curMax;
}
文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. 动态规划
    1. 3.1. 定义
    2. 3.2. 适用情况
    3. 3.3. 解题方法
    4. 3.4. 一般优化思路
  4. 4. 实例
    1. 4.1. 背包问题(Knapsack)
      1. 4.1.1. 01背包问题
      2. 4.1.2. 完全背包问题
    2. 4.2. 装配线调度问题
    3. 4.3. 最大连续子序列
      1. 4.3.1. 之和
      2. 4.3.2. 不超过m之和
      3. 4.3.3. 之积
    4. 4.4. 矩阵链相乘(matrix-chain multiplication)
      1. 4.4.1. 编辑距离(Edit Distance)
    5. 4.5. Shortest reliable paths & Floyd-Warshall algorithm
    6. 4.6. 旅行商问题(Travel Salesman Problem)
    7. 4.7. 最长公共子序列(Longest Common Subsequence)
    8. 4.8. 子集和问题(subset problem)
    9. 4.9. 路径搜索
    10. 4.10. 最长有效括号
      1. 4.10.1.
      2. 4.10.2. 动态规划
|