By

文章目录
  1. 1. 动态规划 (Dynamic Programming)
  2. 2. LCS问题：
  3. 3. 最短路径问题 Floyd-Warshall算法
  4. 4. 参考：

动态规划 (Dynamic Programming)

适用于重叠子问题和最优子结构性质的问题。

大致思路:
待解决一个问题 –> 将其分解成不同部分（即子问题） –> 求解子问题 –> 合并子问题的解，得出原问题的解

最优子结构：局部最优解决定全局最优解

适用情况：

  1. 最优结构性质
  2. 无后效性。即子问题的解一旦确定，就不会改变。
  3. 子问题重叠性质

实例：
斐波那契数列问题
基本算法：

1
2
3
4
function fib(n)
    if n = 0 or n = 1
        return 1
    return fib(n-1) + fib(n-2)

上述的迭代过程很显然有很多重复计算的子问题，这样使程序不够高效。
改进方法：我们可以通过保存已经算出的子问题的解，来避免重复计算，当然这会耗费掉一些内存空间。【空间换取时间】

1
2
3
4
5
array map[0...n] = {0=>0,1=>1}
fib(n)
    if(map m dose not contain key n)
        m[n] := fib(n-1) + fib(n-2)
    return m[n]

使用动态规划的常用算法：

  • 最长单调子序列
  • 最长公共子序列 LCS
  • Floyd-Warshall算法 最短路径问题
  • Viterbi算法

LCS问题：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*******************************************************************
 文件名        ：lcs.cpp
 创建者        ：Monkee
 创建时间      ：2015/8/30 10:34:35
 功能描述      ：动态规划解决LCS问题
              
 ******************************************************************/

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int max(int a,int b)
{
	return (a>b) ? a : b;
}


//最长公共子序列(不要求连续)
//使用一个二维表来存储状态
int LCS1(string x,string y,int m,int n)
{
	vector<vector<int> > matrix(m+1,vector<int>(n+1));
	
	for (int i=0;i<m+1;i++)
	{
		for(int j=0;j<n+1;j++)
		{
			if (i == 0 || j ==0)
			{
				matrix[i][j] = 0;
			} else if(x[i-1] == y[j-1]){
				matrix[i][j] = matrix[i-1][j-1] + 1;
			} else {
				matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1]);
			}

		}
	}
	return matrix[m][n];
}

//最长公共子串
//使用一个一维表来存储状态
int LCS2(string x,string y,int m,int n)
{
	vector<int> array(n);
	int maxl = 0;

	for (int j=0;j<m;j++)
	{
		for (int i=n-1;i>=0;i--)
		{
			if (i==0 || j==0)
			{
				if (x[j] == y[i])
				{
					array[i] = 1;
				} else {
					array[i] = 0;
				}
			} else if (x[j] == y[i])
			{
				array[i] = array[i-1] + 1;
			} else {
				array[i] = 0;
			}

			if (array[i] > maxl)
			{
				maxl = array[i];
			}
		}
	}
	return maxl;
}

int main()
{
	string x = "ABCDEFGH";
	string y = "ABCdfeghEFGH";

	cout<<"最长公共子序列："<<LCS1(x,y,x.length(),y.length())<<endl;
	cout<<"最长公共子串："<<LCS2(x,y,x.length(),y.length())<<endl;
	return 0;
}

最短路径问题 Floyd-Warshall算法

Floyd-Warshall算法，简称Floyd算法，用于求解任意两点间的最短距离，即多源最短路径问题，时间复杂度为O(n^3)，空间复杂度为O(n^2)。

算法代码实现如下：

1
2
3
4
5
6
7
8
void Floyd(){
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(dist[i][k]+dist[k][j]<dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
}

参考：

文章目录
  1. 1. 动态规划 (Dynamic Programming)
  2. 2. LCS问题：
  3. 3. 最短路径问题 Floyd-Warshall算法
  4. 4. 参考：