一.概念介绍
动态规划(Dynamic Programming),简称DP.是把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法.
二.特点
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度,因此它比回溯法、暴力法等要快许多。
在解决问题时,推导出状态转移方程是关键所在.
三.举例
1.最少硬币问题
待续...
2.LCS问题
最长公共子序列的长度问题的推导公式为:
从公式可知,这个问题可以用递归的方式来实现,代码:
1 //递归实现方法 LCS(i,j)即公式中的C[i,j] 2 int LCS(int i, int j) 3 { 4 //第一段 5 if (i==lena || j == lenb) 6 return 0; 7 8 //第二段 9 if (a[i] == b[j]) 10 return 1 + LCS(i + 1, j + 1); 11 else 12 { 13 //第三段 14 int x = LCS(i + 1, j); 15 int y = LCS(i, j + 1); 16 return x > y ? x : y; 17 } 18 }
递归实现虽然好理解,但是存在缺陷,不能记录所有的数据改变的记录,而数据改变的记录可以在长度外,帮助找到子序列.
用数组pd代替公式中的二维数组c[i][j],完成上述公式的代码如下:
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 using namespace std; 5 char a[10], b[10]; 6 int lena, lenb; 7 8 void LCS(); 9 int main() 10 { 11 strcpy_s(a, "ABCBDAB"); 12 strcpy_s(b, "BDCABA"); 13 lena = strlen(a); 14 lenb = strlen(b); 15 16 LCS(); 17 18 int a; 19 cin >> a; 20 return 0; 21 } 22 void LCS() 23 { 24 int m = lena, n = lenb; 25 26 //dp[i][j]存储的是a[i]与b[j]的最长公共子序列的长度 即公式中c[i][j] 27 int dp[11][11]; 28 29 //公式第一段 30 dp[0][0] = 0; 31 for (int i = 0; i < m; i++) 32 { 33 for (int j = 0; j < n; j++) 34 { 35 //如果当前字符相等,公式第二段 36 if (a[i] == b[j]) 37 { 38 dp[i + 1][j + 1] = dp[i][j] + 1; 39 } 40 else 41 { 42 //如果当前的字符不相等 公式第三段 43 dp[i + 1][j + 1] = dp[i + 1][j]>dp[i][j + 1] ? dp[i + 1][j] : dp[i][j + 1]; 44 } 45 } 46 } 47 48 cout << dp[m][n]; 49 cout << endl; 50 }
用数组实现的时候,有一个好处,我们发现了一个规律,相同字符所对应的c[i][j]的赋值一定是它左上侧c[i-1][j-1]的值加一得来的,如下图所示,所以我们通过倒序遍历数组c的赋值过程,可以得到最长自序列.
倒序遍历时,我们需要记载当前c[i][j]被赋值时的方向,引入了一个数组来记载c[i][j]的赋值方向.然后倒序遍历则可以得到结果,代码如下:
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 using namespace std; 5 char a[10], b[10]; 6 int lena, lenb; 7 8 int LCS(int, int); ///两个参数分别表示数组a的下标和数组b的下标 9 void LCS(); 10 int main() 11 { 12 strcpy_s(a, "ABCBDAB"); 13 strcpy_s(b, "BDCABA"); 14 lena = strlen(a); 15 lenb = strlen(b); 16 17 LCS(); 18 19 int a; 20 cin >> a; 21 return 0; 22 } 23 24 void LCS() 25 { 26 int m = lena, n = lenb; 27 28 //dp[i][j]存储的是a[i]与b[j]的最长公共子序列的长度 即公式中c[i][j] 29 int dp[11][11] = { {0} }; 30 //用来记录赋值的方向 31 char dpd[11][11]; 32 33 34 //公式第一段 35 dp[0][0] = 0; 36 for (int i = 0; i < m; i++) 37 { 38 for (int j = 0; j < n; j++) 39 { 40 //如果当前字符相等,公式第二段 41 if (a[i] == b[j]) 42 { 43 dp[i + 1][j + 1] = dp[i][j] + 1; 44 //记录方向 0是左上 45 dpd[i + 1][j + 1] = 0; 46 } 47 else 48 { 49 //如果当前的字符不相等 公式第三段 50 int t; 51 if (dp[i + 1][j]>dp[i][j + 1]) 52 { 53 t = dp[i + 1][j]; 54 //记录方向,1是左边 55 dpd[i + 1][j + 1] = 1; 56 57 } 58 else 59 { 60 t = dp[i][j + 1]; 61 //记录方向,2是上边 62 dpd[i + 1][j + 1] = 2; 63 } 64 65 dp[i + 1][j + 1] = t; 66 } 67 } 68 } 69 70 cout << dp[m][n]; 71 cout << endl; 72 73 while (m>=0&&n >= 0) 74 { 75 //增加子串 76 if (dpd[m][n] == 0 && dp[m][n] > dp[m - 1][n - 1]) 77 { 78 //可以用堆栈记录下来 79 //TODO 80 cout << a[m - 1]<<" "<<b[n-1]<<" "<<endl; 81 } 82 83 switch (dpd[m][n]) 84 { 85 case 0: 86 m--; 87 n--; 88 break; 89 case 1: 90 m--; 91 case 2: 92 n--; 93 default: 94 break; 95 } 96 } 97 98 }
结果:
3.递增子序列问题
递推公示:length[i]=a[i]>a[0...i-1]?length[i-1]+1:max{length[i-1],1}