算法设计与分析复习03：动态规划算法

文章目录

• 算法设计与分析复习03：动态规划算法
• • 复习重点
  • 动态规划算法
  • • 斐波那契数列及其应用
    • 矩阵链乘法+凸多边形剖分
    • • 矩阵链乘法
      • 凸多边形剖分
    • 最长公共子序列
    • 最大子段和（字数组）
    • 0-1背包
    • 编辑距离
    • 钢条切割

复习重点

动态规划算法

斐波那契数列及其应用

时间复杂度为O(2n)O(2^n)O(2n)，随问题规模，呈指数级别增加。

记忆化搜索的时间复杂度为O(n)O(n)O(n)。

动态规划的时间复杂度也为O(n)O(n)O(n)。
不同之处在于，动态规划自底向上进行计算，记忆化搜索自顶向下计算

矩阵链乘法+凸多边形剖分

矩阵链乘法

纯递归方法，根据动态转移方程：

其中，RecurMatrixChain(i, k, s, p)为矩阵i到矩阵k所需要的最少数乘次数。

int RecurMatrixChain(int i, int j, int** s, int* p)
{if (i == j) return 0;int u = INT_MAX;for (int k = i; k < j; k++){int t = RecurMatrixChain(i, k, s, p)+ RecurMatrixChain(k + 1, j, s, p) + p[i - 1] * p[k] * p[j];if (t < u){u = t;s[i][j] = k;}}return u;
}

消除重复计算的方法：

通过一个O(n2)O(n^2)O(n2)的表格进行记录，沿对角线进行计算。
时间复杂度：
O(n3)O(n^3) O(n3)
空间复杂度：
O(n2)O(n^2) O(n2)
核心代码如下：

void MatrixChain(vector& p, int n, vector>& m, vector>& s)
{for (int a = 1; a <= n; a++)m[a][a] = 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] = INT_MAX;for (int k = i; 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] = t; s[i][j] = k;}}}
}

解追溯与测试代码如下：

int Traceback(int i, int j, vector> s) //找出s数组中记录的最优断开点
{if (i == j)return -1;Traceback(i, s[i][j], s);Traceback(s[i][j] + 1, j, s);cout << "包含矩阵A" << s[i][j];cout << "的部分与包含矩阵A" << (s[i][j] + 1)<< "的部分结合，放在一个括号中" << endl;return 0;
}int main() {int n = 6;vector> m(n + 1, vector(n + 1));vector> s(n + 1, vector(n + 1));vector p(n + 1);p = { 5,10,3,12,5,50,6 };MatrixChain(p, n, m, s);for (int i = 0; i < n+1; i++) {for (int j = 0; j < n+1; j++) {cout << "\t" << m[i][j] << "\t";}cout << endl;}cout << endl;for (int i = 0; i < n + 1; i++) {for (int j = 0; j < n + 1; j++) {cout << "\t" << s[i][j] << "\t";}cout << endl;}Traceback(1, n, s);
}

凸多边形剖分

参考leetcode上题leetcode1039：多边形三角剖分的最低得分

其中，按照leetcode1039题目给出的权函数定义，所得最优子结构性质如下：
t[i][j]={0j - i <= 1t[i][k]+t[k][j]+values[i]×values[k]×values[j]j- i > 1t[i][j]=\left\{ \begin{matrix} 0& \text{j - i <= 1} \\ t[i][k]+t[k][j]+values[i]\times{values[k]}\times{values[j]}& \text{ j- i > 1} \end{matrix} \right. t[i][j]={0t[i][k]+t[k][j]+values[i]×values[k]×values[j]​j - i <= 1 j- i > 1​
leetcode1039题解如下：

class Solution {
public:int minScoreTriangulation(vector& values) {int n = values.size();vector> dp(n, vector(n));/*for (int i = 0; i < n; i++) {dp[i][i + 1] = 0;}*/for (int r = 3; r <= n; r++) //r为当前计算的链长（子问题规模）{for (int i = 0; i <= n - r; i++) //n-r+1为最后一个r链的前边界{int j = i + r - 1;  //计算前边界为i，链长为r的链的后边界dp[i][j] = INT_MAX; //将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i//s[i][j] = i;for (int k = i + 1; k < j; k++) {//将链ij划分为( A[i:k] )* (A[k+1:j])int u = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];if (u < dp[i][j]) {dp[i][j] = u;//s[i][j] = k;}}}}return dp[0][n-1];}
};
// 测试用例
int main() {Solution solution;vectorvalues = { 3,7,4,5 };int n = solution.minScoreTriangulation(values);cout << n;
}

最长公共子序列

最优子结构性质：

填表过程：

核心代码：

#include
#include
#include
using namespace std;
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size();int n = text2.size();vector>C(m + 1, vector(n + 1));vector>rec(m + 1, vector(n + 1));for (int i = 1; i < m + 1; i++) {for (int j = 1; j < n + 1; j++) {if (text1[i - 1] == text2[j - 1]) {C[i][j] = C[i - 1][j - 1] + 1;rec[i][j] = 1;}else if (C[i][j - 1] > C[i - 1][j]) {C[i][j] = C[i][j - 1];rec[i][j] = 2;}else {C[i][j] = C[i - 1][j];rec[i][j] = 3;}}}int i = m;int j = n;while (i > 0 && j > 0) {if (rec[i][j] == 1) { cout << text1[i - 1]; i--;j--;}else if (rec[i][j] == 2) {j--;}else {i--;}}return C[m][n];}
};int main() {string text1 = "ybl";string text2 = "yby";Solution solution;int num = solution.longestCommonSubsequence(text1, text2);cout << endl << num;
}

最大子段和（字数组）

状态转移方程：
maxvalue[i]={maxvalue[i−1]+num[i]maxvalue[i-1] + num[i] > maxvalue[i-1] maxvalue[i−1]maxvalue[i-1] + num[i] < maxvalue[i-1] maxvalue[i]=\left\{ \begin{matrix} maxvalue[i-1] + num[i]& \text{ maxvalue[i-1] + num[i] > maxvalue[i-1] } \\ maxvalue[i-1] & \text{ maxvalue[i-1] + num[i] < maxvalue[i-1] } \end{matrix} \right. maxvalue[i]={maxvalue[i−1]+num[i]maxvalue[i−1]​ maxvalue[i-1] + num[i] > maxvalue[i-1]  maxvalue[i-1] + num[i] < maxvalue[i-1] ​

//方法1：
class Solution {
public:int maxSubArray(vector& nums) {int pre = 0;int maxvalue = INT_MIN;for (auto num : nums) {pre = max(pre + num, num);maxvalue = max(maxvalue, pre);}return maxvalue;}
};

0-1背包

问题描述：

状态转移方程：
KnapsackSR(h,i,C)=max(KnapsackSR(h,i−1,C)，KnapsackSR(h,i−1,C−V[i])+P[i])KnapsackSR(h,i,C)=max(KnapsackSR(h,i-1,C)，KnapsackSR(h,i-1,C-V[i])+P[i]) KnapsackSR(h,i,C)=max(KnapsackSR(h,i−1,C)，KnapsackSR(h,i−1,C−V[i])+P[i])
递归求解：


dp求解（填表）：


leetcode416：分割和子集（和0-1背包问题）核心代码：

#include
#include
using namespace std;
class Solution {
public:bool canPartition(vector& nums) {int sum = 0;for (auto num : nums) {sum += num;}if (sum % 2)return false;int C = sum / 2;vector> dp(nums.size(), vector(C + 1));for (int i = 0; i < nums.size(); i++) {for (int j = 1; j < dp[0].size(); j++) {if (i == 0) {dp[i][j] = nums[i] > j ? 0 : nums[i];}else if (j < nums[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);}if (dp[i][dp[0].size() - 1] == C)return true;}return false;}
};int main() {vector nums = { 1,2,5 };Solution solution;cout << solution.canPartition(nums);
}

编辑距离

问题描述：

删除：

插入：

替换：


填表：






追溯解：

leetcode72：编辑距离核心代码：

#include
#include
#include
using namespace std;
class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size() + 1;int n = word2.size() + 1;vector> dp(m, vector(n));for (int i = 0; i < m; i++) {dp[i][0] = i;}for (int j = 0; j < n; j++) {dp[0][j] = j;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];}else {dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),dp[i - 1][j - 1] + 1);}}}return dp[m - 1][n - 1];}
};int main() {string s1 = "horse";string s2 = "ros";Solution solution;int res = solution.minDistance(s1, s2);cout << res;return 0;
}

钢条切割

状态转移方程：

#include
#include
using namespace std;int CutFe(vectorp, int n) {vectorC(n + 1);for (int i = 0; i < n + 1; i++) {int t = i - p.size() + 1;for (int j = max(t, 0); j < i; j++) {//i-p.size()+1C[i] = max(C[i], C[j] + p[i - j]);}}return C[n];
}
int main() {vector p = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 24 };	cout << CutFe(p, 10);return 0;
}