By

Contents
  1. 1. 算法策略
  2. 2. 动态规划
    1. 2.1. 介绍动态规划
    2. 2.2. 解题步骤
    3. 2.3. 例子
  3. 3. 分治
    1. 3.1. 介绍分治
    2. 3.2. 解题步骤
    3. 3.3. 例子
  4. 4. 贪心
    1. 4.1. 介绍贪心算法
    2. 4.2. 解题步骤
  5. 5. 回溯
    1. 5.1. 介绍回溯
    2. 5.2. 解题步骤
    3. 5.3. 例子
  6. 6. 关于算法设计的思路
  7. 7. 附录一
  8. 8. References

算法策略

算法策略是指设计和解决一类问题的通用方法或模板。也可以称为算法范式（Algorithm Paradigm）。常见的算法策略，如动态规划、分治、贪心和回溯等。每个算法策略有它的设计思路，解题步骤。算法策略往往提供了优化算法的功能，使用算法策略比直接法（枚举法，穷举法）有更好的效率。

动态规划

介绍动态规划

动态规划（Dynamic Programming）是一种数学优化方法和一种算法策略。这个方法是 Richard Bellman 在1950 年发明的。它指的是通过递归的方式，将问题分解为更简单的子问题，从而简化一个复杂的问题。

动态规划问题必须具备两个属性：最优子结构和重叠的子问题。如果一个问题有最优子结构，但没有重叠的子问题，那么它是一个分治问题。

最优子结构（Optimal Substructure）。如果一个问题可以通过“将问题分解为子问题和递归地找到子问题的最优解”来最优地解决，那么称它有最优子结构。也可以说，得到一个问题的最优解可以通过子问题的最优解来实现。如果一个问题具有最优子结构，较大问题和它的子问题之间的存在关联，这种关系称为 Bellman 方程。

重叠的子问题（Overlapping Sub-Problem）。求解过程中递归地求解相同的子问题，没有产生新的子问题。也可以说，问题和子问题存在一个固定的关系表达式，如 F(n) = F(n-1) + F(n-2) ，F(n) = F(n-1) * 2 + 1。所有的子问题可以用一个固定的算法代码去实现。

解决动态规划问题的两种方法：

  • 自顶向下方法（Top-down Approach）。将子问题的结果存储在列表中，当我们要解决新的子问题时，我们会首先检查是否已经解决。如果结果已经记录在列表中，可以直接使用它，否则我们解决子问题并将其结果添加到列表中。如：我们可以通过 F(n) = F(n-1) + F(n-2) 得到问题的结果，先检查子问题结果列表中有没有子问题 F(n-1) 和 F(n-2) 的结果，如果有就直接使用，没有就求解这两个子问题。依次往下递归，每个子问题只计算一次。
  • 自底向上方法（Bottom-up Approach）。一旦按照子问题递归地制定了问题地解决方案，我们可以尝试自底向上地去解决问题。自底向上地方法大部分不需要记录每个子问题的结果，只需要替换记录几个需要地子问题结果。具体过程：通过使用较小的子问题的结果迭代生成越来越大的子问题结果。如，已知子问题 F40 和 F41 的结果，可以直接计算出 F42 的结果。

解题步骤

1. 判断一个问题是否是动态规划问题。

判断问题是否具有最优子结构和重叠的子问题等特性。

2. 构造出问题与子问题之间的关系表达式

常见的动态规划问题的子问题关系表达式，见附录一

3. 使用自顶向下或者自底向上求解。

例子

求第 n 个斐波那契数。

直接法简单的解决方法。T(n) = O(n ^ 2), S(n) = O(1)

1
2
3
4
5
6
int fib(int n)
{
	if (n <= 1)
		return n;
	return fib(n-1) + fib(n-2);
}

动态规划自顶向下方法。T(n) = O(n), S(n) = O(n)

1
2
3
4
5
6
7
8
int fib(int n, auto &lookup)
{
	if (n <= 1)
		return n;
	if (lookup.find(n) == lookup.end())
		lookup[n] = fib(n-1, lookup) + fib(n-2, lookup);
	return lookup[n];
}

动态规划自底向上方法。T(n) = O(n), S(n) = O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
int fib(int n)
{
	if (n < 1)
		return n;
	int prev = 0, curr = 1;
	for (int i = 0; i < n-1; i++)
	{
		int newFib = prev + curr;
		prev = curr;
		curr = newFib;
	}
	return curr;
}

分治

介绍分治

分治（Divide and Conquer）是一个基于多分支递归的算法设计范式。它将一个问题递归的分解为两个或多个子问题，直到它们足够简单能够直接求解。

解题步骤

分析问题得到分解策略。

根据分解策略，递归地求解。

例子

参考快速排序、归并排序算法。

贪心

介绍贪心算法

贪心算法（Greedy Algorithm）是一个算法设计范式。它在每个阶段做出局部最优选择，以寻求全局最优。

解题步骤

根据贪心策略一小段一小段的求解，最后得到问题的最优解。

回溯

介绍回溯

回溯（Backtracking）是一种算法范式，用于查找某些计算问题的所有结果。它逐步的构建候选对象，一旦确定候选对象无法得到有效的结果立刻将其放弃。

回溯是解决约束满足问题的重要工具。它可以快速测试是否能得出满足条件的有效结果。如填字游戏，数独，棋盘等问题。回溯算法通常比对所有对象的暴力枚举（Brute Force Enumeration）更有效率，因为它通过一个测试减少了很多候选对象。

常见类型：

  • 路径选择。如：最短路径，是否存在路径，打印所有存在路径。这类问题的背景：迷宫，国际象棋，二维数组，图。

解题步骤

1. 判断是否是一个回溯问题。

2. 设定一个开始点，进行循环遍历。

3. 当前结果是否满足条件。如果是，打印结果。如果不是，循环递归所有的有效的下一个候选对象。

例子

N Queens problem.

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
#include <iostream>
#include <cstring>
using namespace std;

#define N 8

int count = 0;

bool isSafe(char mat[][N], int row, int col)
{
	for (int i = 0; i < row; i++)
	{
		if (mat[i][col] == 'Q')
		{
			return false;
		}
	}
	
	for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
	{
		if (mat[i][j] == 'Q')
		{
			return false;
		}
	}
	
	for (int i = row, j = col; i >= 0 && j < N; i--, j++)
	{
		if (mat[i][j] == 'Q')
		{
			return false;
		}
	}
	
	return true;
}

void NQueen(char mat[][N], int row)
{	
	if (row == N)
	{
		cout << ++count << endl;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cout << mat[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
		return;
	}
	
	// place Queen at every square in current row r
    // and recur for each valid movement 
	for (int k = 0; k < N; k++)
	{
		if (isSafe(mat, row, k))
		{
			// place queen on current square
			mat[row][k] = 'Q';
			// recur for next row
			NQueen(mat, row+1);
			// backtrack and remove queen from current square 
			mat[row][k] = '-';
		}
	}
	return;
}

int main()
{
	// mat[][] keeps track of position of Queens in current configuration
	char mat[N][N];
	
	// initalize mat[][] by '-'
    memset(mat, '-', sizeof mat);
	
	int row = 0;
	NQueen(mat, row); // N=8 has 92 possible N-Queen result 
	return 0;
}

关于算法设计的思路

1. 思考问题的直接法的解决方法。

2. 考虑优化。是否存在大量重复的操作？是否存在不必要的操作？

3. 考虑算法设计策略。

问题的局部最优解能不能得到全局最优。如果能，考虑使用贪心算法。

问题能不能递归地分解为子问题求解（是否具有最优子结构）。如果能，考虑使用分治法，或者动态规划。

附录一

常见的动态规划问题的子问题关系表达式。

Fibonacci

1
2
3
         | n                  (n <= 1)
Fib(n) = |
         | Fib(n-1) + F(n-2)   (n > 1)

Longest Common Subsequence (LCS)

1
2
3
             | 0                              (i == 0 or j == 0)
LCS[i][j] =  | LCS[i-1][j-1] + 1              (X[i-1] = Y[j-1])
             | max(LCS[i-1][j], LCS[i][j-1])  (X[i-1] != Y[j-1])

Shortest Common Supersequence (SCS)

1
2
3
             | i+j                            (i=0 or j=0)
SCS[i][j] =  | SCS[i-1][j-1] + 1              (X[i-1] = Y[j-1])
             | min(SCS[i-1][j] + 1, SCS[i][j-1] + 1)  (X[i-1] != Y[j-1])

Longest Increasing Subsequence (LIS)

1
2
3
         | 1    (n=1)
LIS(n) = | 
         | max(L(i))    0 < i <= n

The Levenshtein distance (Edit distance)

1
2
3
4
5
6
7
             | max(i, j)                       when min(i, j) = 0
             
dist[i][j] = | dist[i - 1][j - 1]              when X[i-1] == Y[j-1]
             
             | 1 + minimum { dist[i - 1][j],   when X[i-1] != Y[j-1]
             |               dist[i][j - 1],
             |               dist[i - 1][j - 1] }

References

[1] Dynamic programming - Wikipedia

[2] How to solve a Dynamic Programming Problem ? - Geeksforgeeks

[3] Introduction to Dynamic Programming - Techie Delight

[4] Divide-and-conquer algorithm - Wikipedia

[5] Backtacking - Wikipedia

Contents
  1. 1. 算法策略
  2. 2. 动态规划
    1. 2.1. 介绍动态规划
    2. 2.2. 解题步骤
    3. 2.3. 例子
  3. 3. 分治
    1. 3.1. 介绍分治
    2. 3.2. 解题步骤
    3. 3.3. 例子
  4. 4. 贪心
    1. 4.1. 介绍贪心算法
    2. 4.2. 解题步骤
  5. 5. 回溯
    1. 5.1. 介绍回溯
    2. 5.2. 解题步骤
    3. 5.3. 例子
  6. 6. 关于算法设计的思路
  7. 7. 附录一
  8. 8. References