1 分治与递归 1.1 阶乘函数
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # include <iostream> using namespace std;int factorial (int n) { if (n == 0 ) return 1 ; else return n * factorial (n - 1 ); } int main () { int n; cin >> n; cout << factorial (n) << endl; return 0 ; }
1.2 Fibonacci数列
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 # include <iostream> using namespace std;int fibonacci (int n) { if (n <= 1 ) return 1 ; return fibonacci (n-1 ) + fibonacci (n-2 ); } int main () { int n; cin >> n; cout << fibonacci (n) << endl; return 0 ; }
1.3 全排列问题
思路:
定义函数perm(int list[], int k, int m)
表示获取list[k:m]
的全排列。
递归条件:
当n=1
时,全排列只有一种,即为它本身。
当n>1
时,可以依次将每一个数作为前缀,然后对后续n-1
个数进行全排列。
代码:
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 # include <iostream> using namespace std;void swap (int &a, int &b) { int tmp = a; a = b; b = tmp; } int perm (int list[], int k, int m) { if (k == m) { for (int i =0 ;i <=m;i++){ cout << list[i]; } cout << endl; } else { for (int i = k; i<=m; i++) { swap (list[k], list[i]); perm (list, k+1 , m); swap (list[k], list[i]); } } } int main () { int a[] = {1 ,2 ,3 }; perm (a, 0 , 2 ); return 0 ; }
1.4 整数划分问题
(1)递归解法
思路:
对于$q(n,m)$:
代码:
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 #include <iostream> using namespace std;int q (int n, int m) { if (n == 1 || m == 1 ) { return 1 ; } if (n < m) { return q (n, n); } if (n == m) { return 1 + q (n, m - 1 ); } if (n > m) { return q (n - m, m) + q (n, m - 1 ); } } int main (int argc, char const *argv[]) { int n,m; cin >> n >> m; cout << q (n,m) << endl; return 0 ; }
(2)动态规划解法
TODO
1.5 棋盘覆盖问题
思路:
分治法将棋盘划分为四个区域,从而得到四个子问题进行解决。
特殊方格必然位于四个区域中的其中一个,但是另外三个区域则没有特殊方格,导致了子问题不相同。因此,可以假设先用一个L型骨牌放在四个区域的交界处当作特殊方格,从而使每一个区域内都存在一个特殊方格,如下图所示:
通过这样的分割和假设,棋盘分割问题就可以转化为四个1/4规模的子问题。
代码:
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 #include <cstdio> #include <vector> int tile = 0 ; int Board[100 ][100 ] = {0 }; void ChessBoard (int tr, int tc, int dr, int dc, int size) { if (size == 1 ) return ; int t = ++tile; int s = size / 2 ; if (dr < tr + s && dc < tc + s) { ChessBoard (tr, tc, dr, dc, s); } else { Board[tr + s - 1 ][tc + s - 1 ] = t; ChessBoard (tr, tc, tr + s - 1 , tc + s - 1 , s); } if (dr < tr + s && dc >= tc + s) { ChessBoard (tr, tc + s, dr, dc, s); } else { Board[tr + s - 1 ][tc + s] = t; ChessBoard (tr, tc + s, tr + s - 1 , tc + s, s); } if (dr >= tr + s && dc < tc + s) { ChessBoard (tr + s, tc, dr, dc, s); } else { Board[tr + s][tc + s - 1 ] = t; ChessBoard (tr + s, tc, tr + s, tc + s - 1 , s); } if (dr >= tr + s && dc >= tc + s) { ChessBoard (tr + s, tc + s, dr, dc, s); } else { Board[tr + s][tc + s] = t; ChessBoard (tr + s, tc + s, tr + s, tc + s, s); } } int main () { int size = 8 ; int special_row = 3 ; int special_col = 4 ; ChessBoard (0 , 0 , special_row, special_col, size); for (int i = 0 ; i < size; i++) { for (int j = 0 ; j < size; j++) { printf ("%2d " , Board[i][j]); } printf ("\n" ); } return 0 ; }
1.6 归并排序 递归的解法:
先对nums[l:m]
进行排序,再对nums[m+1:r]
进行排序。
将排好序的两部分合并,合并的时候先创建一个临时tmp
,然后依次比较两部分的数值大小,将较小的放入tmp
,然后移动指针;如果某一部分的元素已经全部放入,将另一部分剩余元素直接放入即可。
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 # include <cstdio> # include <vector> using namespace std;void merge (vector<int > &nums, int l, int m, int r) { vector<int > tmp (r - l + 1 ) ; int i = l, j = m + 1 ; int cnt = 0 ; while (i <= m && j <= r) { if (nums[i] <= nums[j]) { tmp[cnt++] = nums[i++]; } else { tmp[cnt++] = nums[j++]; } } while (i <= m) { tmp[cnt++] = nums[i++]; } while (j <= r) { tmp[cnt++] = nums[j++]; } for (int i = 0 ; i < r - l + 1 ; i++) { nums[i + l] = tmp[i]; } } void mergeSort (vector<int > &nums, int l, int r) { if (l >= r) return ; int m = (l + r) / 2 ; mergeSort (nums, l, m); mergeSort (nums, m + 1 , r); merge (nums, l, m, r); } int main () { vector<int > a{2 , 4 , 6 , 2 , 3 , 5 , 8 }; mergeSort (a, 0 , (int )a.size () - 1 ); for (auto i:a){ printf ("%d " , i); } return 0 ; }
整数因子分解问题
1 2 3 4 5 6 1: 1 2: 2 3: 3 4: 4 2*2 5: 5 6: 6 2*3 3*2
(1)解法一:递归
思路:
当n=1
时,只有一种分解方式。
当n>1
时,solve(n)
可以对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 #include <iostream> using namespace std;int result = 0 ;void solve (int n) { if (n == 1 ) { result++; } else { for (int i = 2 ; i <= n; i++) { if (n % i == 0 ) { solve (n/i); } } } } int main () { solve (12 ); cout << result << endl; return 0 ; }
(2)解法二:动态规划
2 数据结构 3 动态规划 3.1 矩阵连乘问题
(1)最优子结构
将$A_i A_{i+1} \dots A_j$的矩阵连乘定义为$A[i:j]$,那么现假设在位置$k$ 加括号使$A[i:j]=A[i:k]A[k+1:j]$,那么总计算量就等于$A[i:k]$的计算量加上$A[k+1:j]$的计算量,再加上这矩阵相乘的计算量$p_{i-1}p_k p_j$。
并且,计算$A[i:j]$的最优次序所包含的计算矩阵子链$A[1:k]$和$A[k+1:j]$的次序也是最优的,即具有最优子结构性质 。
反证:如果$k$不是最优的,即存在一个更好的划分位置$k’$使$A[1:k’]$或$A[k’+1:j]$的计算量更少,那么得到的$A[1:n]$计算量也会比最优次序的计算量更少,导致矛盾。
(2)建立递归关系
用$m[i][j]$存储$A[i][j]$的最优次序计算量,则原问题的最优值为$m[1][m]$。
当$i=j$时,只有一个矩阵,因此$m[i][j]=0$
当$i<j$时,假设在$k$断开,则$m[i][j]=m[i][k]+m[k+1][j]+p_{i-1} p_k p_j$,由于$k$的位置不确定,因此这里需要取$min$。
递归式如下: $$ m[i][j]= \begin{cases}0 & i=j \ \min {i \leqslant k<j}\left{m[i][k]+m[k+1][j]+p {i-1} p_{k} p_{j}\right} & i<j\end{cases} $$ 除此之外,还可以顶一个$s[i][j]$用来存储最优断开位置$k$,在计算出最优值$m[i][j]$后,可递归地由$s[i][j]$构造出相应的最优解。
(3)构造最优解
s[i][j]
记录了A[i:j]
最佳断开的位置k
,因此当求解A[1:n]
的最优加括号方式,只需要递归得查找A[i:k]
和A[k+1][j]
得最优加括号方式,即A[1:s[1][n]]
和A[s[1][n]+1: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 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <iostream> #include <vector> using namespace std;void MatrixChain (vector<int > &p, int n, vector<vector<int >> &m, vector<vector<int >> &s) { for (int i = 0 ; i < n; i++) { m[i][i] = 0 ; } for (int r = 2 ; r <= n; r++) { for (int i = 1 ; i <= n - r + 1 ; i++) { int j = i + r - 1 ; m[i][j] = m[i + 1 ][j] + p[i - 1 ] * p[i] * p[j]; s[i][j] = i; for (int k = i + 1 ; k < j; k++) { int t = m[i][k] + m[k + 1 ][j] + p[i - 1 ] * p[k] * p[j]; if (t < m[i][j]) { m[i][j] = i; s[i][j] = k; } } } } } void Traceback (int i, int j, vector<vector<int >> &s) { if (i == j) return ; Traceback (i, s[i][j], s); Traceback (s[i][j] + 1 , j, s); cout << "Multiply A " << i << ", " << s[i][j]; cout << " and A" << s[i][j] + 1 << ", " << j << endl; } int main () { vector<int > p{30 , 35 , 35 , 15 , 15 , 5 , 5 , 10 , 10 , 20 , 20 , 25 }; vector<vector<int >> m (12 , vector <int >(12 , 0 )); vector<vector<int >> s (12 , vector <int >(12 , 0 )); MatrixChain (p, 6 , m, s); Traceback (1 , 6 , s); return 0 ; }
3.2 最长公共子序列
(1)最优子结构
设序列$X_m={x_1,x_2,\dots,x_m}$和$Y_n={y_1,y_2,\dots,y_n}$的最长公共子序列为$Z_k={z_1,z_2,\dots,z_k}$,可以从后往前看:
如果$x_m=y_n$,那么这个数一定在公共子序列中,即$z_k=x_m=y_n$,那么原问题的规模下降为求解$X_{m-1}$和$Y_{n-1}$的最长公共子序列$Z_{k-1}$
如果$x_m \neq y_n$且$z_k \neq x_m$,那么$x_m$一定不在公共子序列中,因此原问题规模可以下降为求解$X_{m-1}$和$Y_n$的最长公共子序列$Z_k$
如果$x_m \neq y_n$且$z_k \neq y_n$,那么$y_n$一定不在公共子序列中,因此原问题规模可以下降为求解$Y_{n-1}$和$X_m$的最长公共子序列$Z_k$
反证:
如果$z_k \neq x_m$,那么也就说明$z_k$后面还有一个公共数,即${z_1,z_2,\dots,z_k,x_m}$,那么此时公共子序列的长度为$k+1$,与$Z_k$是$X$和$Y$的最长公共子序列矛盾,因此必有$z_k=x_m=y_n$。同样的,如果$X_{m-1}$和$Y_{n-1}$有长度大于$k-1$的公共子序列$W$,那么将$x_m=y_n$加在该序列末尾,会导致$X_m$和$Y_n$的最长公共子序列长度大于$k$,矛盾。因此,$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的最长公共子序列。
因为$z_k \neq x_m$,$Z_k$是$X_{m-1}$和$Y$的公共子序列,若$X_{m-1}$和$Y$有长度大于$k$的公共子序列$W$,则$W$应该也是$X_m$和$Y_n$的公共子序列,与$Z_k$是$X_m$和$Y_n$最长公共子序列矛盾。
因此,最长公共子序列问题包含了两个序列前缀的最长公共子序列的子问题,且具有最优子结构的性质。
(2)构造递归方程
如果$x_m=y_n$,那么这个数一定在公共子序列中,此时只需要找到$X_{m-1}$和$Y_{m-1}$的最长公共子序列,再在其末尾加上$x_m(x_m=y_n)$即可。
如果$x_m \neq y_n$,那么就需要在$X_{m-1}$和$Y_n$以及$X_m$和$Y_{n-1}$两个最长公共子序列子问题中,找出更大的那个序列。
递归方程如下,$c[i][j]$表示$X_i$与$Y_j$的最长公共子序列长度: $$ c[i][j]= \begin{cases} 0 & i>0 ; j=0 \ c[i-1][j-1]+1 & i, j>0 ; x_{i}=y_{i} \ \max {c[i][j-1], c[i-1][j]} & i, j>0 ; x_{i} \neq y_{i}\end{cases} $$ (3)最优解
如果除了LCS的长度,还想获取具体的LCS序列,则还需要一个$b[i][j]$用来记录当前采取了那种子问题,从而在构造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 #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std;void LCSLength (int m, int n, string x, string y, vector<vector<int >> &c, vector<vector<int >> &b) { for (int i = 0 ; i <= m; i++) { for (int j = 0 ; j <= n; j++) { if (i == 0 || j == 0 ) { c[i][j] = 0 ; } else if (x[i - 1 ] == y[j - 1 ]) { c[i][j] = c[i - 1 ][j - 1 ] + 1 ; b[i][j] = 1 ; } else if (c[i - 1 ][j] > c[i][j - 1 ]) { c[i][j] = c[i - 1 ][j]; b[i][j] = 2 ; } else { c[i][j] = c[i][j - 1 ]; b[i][j] = 3 ; } } } } void LCS (int i, int j, string x, vector<vector<int >> &b) { if (i == 0 || j == 0 ) return ; if (b[i][j] == 1 ) { LCS (i - 1 , j - 1 , x, b); cout << x[i - 1 ]; } else if (b[i][j] == 2 ) { LCS (i - 1 , j, x, b); } else { LCS (i, j - 1 , x, b); } } int main () { string x = "abcfbc" ; string y = "abfcab" ; int m = x.size (); int n = y.size (); vector<vector<int >> c (m + 1 , vector <int >(n + 1 , -1 )); vector<vector<int >> b (m + 1 , vector <int >(n + 1 , -1 )); LCSLength (m, n, x, y, c, b); cout << c[m][n] << endl; LCS (m, n, x, b); return 0 ; }
3.3 最大字段和
(1)分治法:
将原问题$a[1:n]$的最大子段和分解为$a[1:n/2]$和$a[n/2+1,n]$的两个子问题,分别求这两个子问题的最大子段和。
在这两个子问题进行合并的时候,会存在以下三种情况:
$a[1:n]$的最大子段和与子问题$a[1:n/2]$的最大子段和相同。
$a[1:n]$的最大子段和与子问题$a[n/2+1:n]$的最大子段和相同。
$a[1:n]$的最大子段和$\sum_{k=i}^j{a_k}$的开始位置$i<n/2$,结束位置$j>n/2+1$。
对于前两种情况,直接递归求解即可。对于第三种情况,$a[n/2]$和$a[n/2+1]$肯定在最优子段中,那么只需从位置$n/2$分别向前、向后找到最大的子段,也就是 $$ 最大子段和=\max_{1 \leq i \leq n/2} \sum_{k=i}^{n/2}a[k] + \max_{n/2+1 \leq i \leq n} \sum_{k=n/2+1}^{j}a[k] $$
复杂度分析:子问题规模为$n/2$,合并需要$O(n)$,递归式如下,解得$T(n)=O(n\log{n})$ $$ T(n) = \begin{cases} O(1) & n \leq c \ 2T(n/2) + O(n) & n \gt c
\end{cases} $$
代码:
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 #include <iostream> #include <vector> #include <algorithm> using namespace std;int MaxSubSum (vector<int > &a, int left, int right) { int sum = 0 ; if (left == right) { sum = a[left] > 0 ? a[left] : 0 ; } else { int mid = (left + right) / 2 ; int leftSubSum = MaxSubSum (a, left, mid); int rightSubSum = MaxSubSum (a, mid + 1 , right); int s1 = 0 ; int leftSum = 0 ; for (int i = mid; i >= left; i--) { leftSum += a[i]; } if (leftSum > s1) { s1 = leftSum; } int s2 = 0 ; int rightSum = 0 ; for (int i = mid + 1 ; i <= right; i++) { rightSum += a[i]; } if (rightSum > s2) { s1 = rightSum; } sum = leftSum + rightSum; if (sum < leftSum) { sum = leftSum; } if (sum < rightSum) { sum = rightSum; } } return sum; } int maxSum (int n, vector<int > &a) { return MaxSubSum (a, 1 , n); } int main () { int res; vector<int > a{-2 , 11 , -4 , 13 , -5 , -2 }; res = maxSum (6 , a); cout << "res:" << res << endl; return 0 ; }
(2)动态规划
设$b[i-1]$表示$a[1:i-1]$的最大子段和,那么对于第$i$个元素$a[i]$来说,它要么合并到$a[1:i-1]$的最大子段中,要么重新成为一个新的子段,取决于$b[i-1]+a[i]$和$a[i]$的大小。
因此,动态规划的递归式如下: $$ b[i] = \max { b[i-1] + a[i], a[i]},\space 1 \leq i \leq n $$ 该方法只需要遍历一次序列,复杂度为$O(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 #include <iostream> #include <vector> #include <algorithm> using namespace std;int maxSum (int n, vector<int > &a) { int prev = 0 , maxSum = a[0 ]; for (const auto x:a) { prev = max (prev + x, x); maxSum = max (prev, maxSum); } return maxSum; } int main () { int res; vector<int > a{-2 , 11 , -4 , 13 , -5 , -2 }; res = maxSum (6 , a); cout << "res:" << res << endl; return 0 ; }
动态规划的遍历方式通常是以序列的结束节点为基准,如下:
3.4 凸多边形最优三角剖分 3.5 多边形优秀 3.6 图像压缩 3.7 电路布线 3.8 流水作业调度 3.9 0-1背包问题 3.10 最优二叉搜索树