1 动态规划
1.1 定义
动态规划的核心是状态和状态转移方程。
在记忆化搜索中,可以为正在处理的表项声明一个引用,简化对它的读写操作;
动态规划解决的是多阶段决策问题;
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
和分治法最大的区别在于:适合于用动态规划的问题,经过分解以后得到的子问题往往不是相互独立的(即下一个子阶段的求解是建立在上一个子阶段的基础之上,进行进一步的求解,而不是相互独立的问题)
动态规划问题一般由难到易分为一维动态规划,二维动态规划,多维动态规划,以及多变量动态规划问题。其中多维动态规划问题又可以进行降维。动态规划问题求解的最重要的一步就是求解出 状态转移方程
1.2 特性
最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理.
无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关
有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势,动态规划可以避免多次计算)
1.3 例子
还是做题最实在!
1.3.1 最长公共子序列
问题描述:给定两个序列:X[1...m]和Y[1...n],求在两个序列中同时出现的最长子序列的长度。
如果按照最普通的方法,就是遍历所有可能的情况(将较短字符串中所有的子串和较长字符串中的子串进行比较),取所有可能的情况中最长的子串;
int DP::LongestCommonSubsequence(string &X, string &Y, int m, int n) { if (m == 0 || n == 0) { return 0; } if (X[m-1] == Y[n-1]) { return LongestCommonSubsequence(X, Y, m-1, n-1) + 1; } else { return max(LongestCommonSubsequence(X, Y, m-1, n), LongestCommonSubsequence(X, Y, m, n-1)); } }void DP::testLongestCommonSubstring() { string x = "abcdefg", y = "efg"; int result = LongestCommonSubsequence(x, y, (int)x.size(), (int)y.size()); cout << "result:" << result; }
很显然,这花费的时间是指数级的,非常慢;
那么采用动态规划是怎么做的?
思路:我们可以想象成树,两个字符串都分别进行发散,对于一个结点来说,左边是左边的字符串进行改变,右边则是右边的字符串进行改变,直到两个字符串都相等。
第一步应该是找出递推公式:
这里的 C[i,j]
代表的意思是字符串 X
中到达下标 i
和字符串 Y
中到达下标 j
的时候的最长子串个数;
第二步是写出伪代码
LCS(x,y,i,j) if x[i] = y[j] then C[i,j] ← LCS(x,y,i-1,j-1)+1 else C[i,j] ← max{LCS(x,y,i-1,j),LCS(x,y,i,j-1)} return C[i,j]
最后是写出代码
上面的伪代码对于每一种情况都会往前重新计算一遍,完全没有必要,用一个数组保存之前计算的值即可;
int DP::LongestCommonSubsequence(string &X, string &Y, int m, int n) { vector<vector<int>> dp(X.size() + 1, vector<int>(Y.size() + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 因为是从1开始的,所以字符串下标要减去1 if (X[i-1] == Y[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }void DP::testLongestCommonSubsequence() { string x = "abcdefg", y = "efg"; int result = LongestCommonSubsequence(x, y, (int)x.size(), (int)y.size()); cout << "result:" << result; }
看看dp数组:
0 0 0 0 0 0 0 1 1 1 1 1 0 1 2 2 2 2 0 1 2 3 3 3 0 1 2 3 3 3 0 1 2 3 3 3 0 1 2 3 4 4 0 1 2 3 4 5
1.3.2 最长公共子串
和上面最长公共子序列不同的是,子串要求连续,不像子序列只要顺序保证是正确的就行了,所以使用一个变量来记录;
/************************************** * // 最长公共子串问题 ***************************************/int DP::LongestCommonSubstring(string &X, string &Y, int m, int n) { vector<vector<int>> dp(X.size() + 1, vector<int>(Y.size() + 1, 0)); int max = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 因为是从1开始的,所以字符串下标要减去1 if (X[i-1] == Y[j-1]) { if (dp[i-1][j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = 1; } if (dp[i][j] > max) { max = dp[i][j]; } } } } for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { cout << " " << dp[i][j]; } cout << endl; } return max; }void DP::testLongestCommonSubstring() { string x = "abcdefg", y = "abcfg"; int result = LongestCommonSubstring(x, y, (int)x.size(), (int)y.size()); cout << "result:" << result << endl; }
看看dp数组:
0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2
可以发现,对角线上连续大于0的值则为长度;最长的子串为abc
,长度为3,次长为fg
,长度为2;
1.3.3 最长递增子序列
问题描述:给定一个序列:X[1...m],求在这个序列中出现的最长递增子序列的长度。
/************************************** * // 最长递增子串问题 ***************************************/int DP::LongestIncreasingSubstring(string &X, int m) { vector<int> dp(X.size(), 0); int max = 0; for (int i = 0; i < m; i++) { //到达 dp[i] = 1; for (int j = 0; j < i; j++) { if (X[i] > X[j]) { dp[i] = dp[j] + 1; } else { //因为是连续的,所以只要不符合就重置 dp[i] = 1; } } } for (int i = 0; i < m; i++) { cout << " " << dp[i]; if (dp[i] > max) { max = dp[i]; } } cout << endl; return max; }void DP::testLongestIncreasingSubstring() { string x = "babcak"; int result = LongestIncreasingSubstring(x, (int)x.size()); cout << "result:" << result << endl; }
1.3.4 矩阵链乘积
题目描述
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
思路
对于矩阵连乘问题,最优解就是找到一种计算顺序,使得计算次数最少;
假设 dp[i, j]
表示第 i 个矩阵到达第 j 个矩阵这段的最优解;
将矩阵连乘积 简记为A[i:j] ,这里i<=j.假设这个最优解在第k处断开,i<=k<j,则A[i:j]是最优的,那么A[i,k]和A[k+1:j]也是相应矩阵连乘的最优解。把i到j分成两部分,看哪种分法乘的次数最少,而k就是i到j中断开的部分,也就是两个括号中间的部分;
状态转移方程
当i=j时,A[i,j]=Ai, m[i,j]=0;(表示只有一个矩阵,如A1,没有和其他矩阵相乘,故乘的次数为0) 当i<j时,m[i,j]=min{m[i,k]+m[k+1,j] +pi-1*pk*pj} ,其中 i<=k<j
也就是
实现
/************************************** * // 矩阵链乘积,求最小乘积次数 ***************************************/void DP::MatrixChainMultiplication(vector<int> data, int n,vector<vector<int>>& m_dp, vector<vector<int>>& s_dp) { //矩阵段长度为1,则 dp[][] 中对角线的值为0,表示只有一个矩阵,没有相乘的. for(int i = 1;i<=n;i++) m_dp[i][i] = 0; // 从第二个开始(第一个也是0),当前的乘次数取决于下一个的乘次数 // 对角线循环,r表示矩阵的长度(2,3…逐渐变长) for(int r = 2;r<=n;r++) { // 行循环 for(int i = 1; i<=n-r+1; i++) { // 列的控制,当前矩阵段(Ai~Aj)的起始为Ai,尾为Aj int j = r+i-1; //例如对(A2~A4),则i=2,j=4,下面一行的m[2][4] = m[3][4]+p[1]*p[2]*p[4],即A2(A3A4) m_dp[i][j] = m_dp[i+1][j] + data[i-1]*data[i]*data[j]; //计算次数 s_dp[i][j] = i;//记录断开点的索引 //循环求出(Ai~Aj)中的最小数乘次数,遍历所有可能的情况 for(int k = i+1 ; k<j;k++) { //将矩阵段(Ai~Aj)分成左右2部分(左m[i][k],右m[k+1][j]) //再加上左右2部分最后相乘的次数(p[i-1] *p[k]*p[j]) int t = m_dp[i][k] + m_dp[k+1][j] + data[i-1] *data[k]*data[j]; if(t < m_dp[i][j]) { m_dp[i][j] = t; s_dp[i][j] = k; //保存最小的,即最优的结果 } } } } }void DP::testMatrixChainMultiplication() { vector<int> data = {30,35,15,5,10,20,25};//记录6个矩阵的行和列,注意相邻矩阵的行和列是相同的 vector<vector<int>> m_dp(7, vector<int>(7, 0));//存储第i个矩阵到第j个矩阵的计算代价(以乘法次数来表示) vector<vector<int>> s_dp(7, vector<int>(7, 0));//存储第i个矩阵到第j个矩阵的最小代价时的分为两部分的位置 int n=6;//矩阵个数 MatrixChainMultiplication(data, n , m_dp, s_dp); cout << "---计算代价---" << endl; for (int i = 0; i < m_dp.size(); i++) { for (int j = 0; j < m_dp[0].size(); j++) { cout << " " << m_dp[i][j]; } cout << endl; } cout << "---最小代价时分为两边的位置" << endl; for (int i = 0; i < s_dp.size(); i++) { for (int j = 0; j < s_dp[0].size(); j++) { cout << " " << s_dp[i][j]; } cout << endl; } }
运行结果为:
---计算代价--- 0 0 0 0 0 0 0 0 0 15750 7875 9375 11875 15125 0 0 0 2625 4375 7125 10500 0 0 0 0 750 2500 5375 0 0 0 0 0 1000 3500 0 0 0 0 0 0 5000 0 0 0 0 0 0 0 ---最小代价时分为两边的位置 0 0 0 0 0 0 0 0 0 1 1 3 3 3 0 0 0 2 3 3 3 0 0 0 0 3 3 3 0 0 0 0 0 4 5 0 0 0 0 0 0 5 0 0 0 0 0 0 0
表示第i个矩阵到第j个矩阵的计算代价矩阵m[i][j]和表示第i个矩阵到第j个矩阵的最小代价时的分为两部分的位置矩阵s[i][j]的结果如下图:
从上面左图的m矩阵可以看出任意第i个到第j个矩阵连乘的乘法次数。最终的加括号形式为:(A1(A2A3))((A4A5)A6)
1.3.5 数塔问题
问题描述:
数塔第i层有i个结点,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
用二维数组则为:
912 1510 6 82 18 9 519 7 10 4 16
假设9首先被输入,是第 0
层,越往下层数不断递增;
思路
为了保证整条路径的和是最大的,下一层的走向取决于再下一层上的最大值是否已经求出才能决定,所以要做一个自顶向下的分析,自底向上的计算;
状态转移方程
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]
dp[i+1][j]
为左结点,dp[i+1][j+1]
为右结点;
实现
/************************************** * // 数塔问题 ***************************************/int DP::MaxSumTower(vector<vector<int>> nums, int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); // 用底层的值来初始化dp,m为行,n为列 for (int i = 0; i < n; i++) { dp[m-1][i] = nums[m-1][i]; } // 自底向上,父结点的最大值取决于左结点或者右结点的最大值 for (int i = m-2; i >= 0; i--) { for (int j = 0; j < n; j++) { if (i >= j) { //过滤多余的 dp[i][j] = std::max(dp[i+1][j], dp[i+1][j+1]) + nums[i][j]; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cout << " " << dp[i][j]; } cout << endl; } return dp[0][0]; }
1.3.6 01背包问题
题目描述
有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?
思路
dp[x][y]
表示体积不超过 y 且可选前 x 种物品的情况下的最大总价值
递归关系:
mp[0][y] = 0
mp[x][0] = 0
当 v[x] > y 时,mp[x][y] = mp[x-1][y]
当 v[x] <= y 时,mp[x][y] = max{ mp[x-1][y], p[x] + mp[x-1][y-v[x]] }
解释如下:
表示体积不超过 y 且可选前 0 种物品的情况下的最大总价值,没有物品可选,所以总价值为 0
表示体积不超过 0 且可选前 x 种物品的情况下的最大总价值,没有物品可选,所以总价值为 0
因为 x 这件物品的体积已经超过所能允许的最大体积了,所以肯定不能放这件物品, 那么只能在前 x-1 件物品里选了
x 这件物品可能放入背包也可能不放入背包,所以取前两者的最大值就好了, 这样就将前两种情况都包括进来了
实现
/************************************** * // 01背包问题 ***************************************/int DP::ZeroOneBackpack(vector<Goods> goods, int limit_weight) { int m = goods.size(); int n = limit_weight; vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 没有选择物品的时候价值为0 for (int i = 1; i < n; i++) { dp[0][i] = 0; } // 重量为0的时候什么物品都选不了,价值自然也为0 for (int i = 1; i < m; i++) {
http://www.cnblogs.com/George1994/p/6710675.html