作者：非妃是公主
专栏：《算法》
个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩
专栏系列文章
复习重点
动态规划算法
斐波那契数列及其应用
递归方法实现斐波那契数列：
n=5时，fib(5)的计算过程
时间复杂度为
O
(
2
n
)
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;
}
直接递归中右大量重复计算：
消除重复计算的方法：MatrixChain运行举例
通过一个
O
(
n
2
)
O(n^2)
O(n2)的表格进行记录，沿对角线进行计算。
时间复杂度：
O
(
n
3
)
O(n^3)
O(n3)
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
核心代码如下：
void MatrixChain(vector<int>& p, int n, vector<vector<int>>& m, vector<vector<int>>& 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<vector<int>> 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<vector<int>> m(n + 1, vector<int>(n + 1));
vector<vector<int>> s(n + 1, vector<int>(n + 1));
vector<int> 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
]
=
{
0
j – i <= 1
t
[
i
]
[
k
]
+
t
[
k
]
[
j
]
+
v
a
l
u
e
s
[
i
]
×
v
a
l
u
e
s
[
k
]
×
v
a
l
u
e
s
[
j
]
j- i > 1
t[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<int>& values) {
int n = values.size();
vector<vector<int>> dp(n, vector<int>(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;
vector<int>values = { 3,7,4,5 };
int n = solution.minScoreTriangulation(values);
cout << n;
}
最长公共子序列
最优子结构性质：
填表过程：
核心代码：
#include<string>
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>>C(m + 1, vector<int>(n + 1));
vector<vector<int>>rec(m + 1, vector<int>(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;
}
最大子段和（字数组）
状态转移方程：
m
a
x
v
a
l
u
e
[
i
]
=
{
m
a
x
v
a
l
u
e
[
i
−
1
]
+
n
u
m
[
i
]
maxvalue[i-1] + num[i] > maxvalue[i-1]
m
a
x
v
a
l
u
e
[
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<int>& 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背包
问题描述：
状态转移方程：
K
n
a
p
s
a
c
k
S
R
(
h
,
i
,
C
)
=
m
a
x
(
K
n
a
p
s
a
c
k
S
R
(
h
,
i
−
1
,
C
)
，
K
n
a
p
s
a
c
k
S
R
(
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<vector>
#include<iostream>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (auto num : nums) {
sum += num;
}
if (sum % 2)return false;
int C = sum / 2;
vector<vector<int>> dp(nums.size(), vector<int>(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];
else
dp[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<int> nums = { 1,2,5 };
Solution solution;
cout << solution.canPartition(nums);
}
编辑距离
问题描述：
删除：
插入：
替换：
填表：
追溯解：
leetcode72：编辑距离核心代码：
#include<string>
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size() + 1;
int n = word2.size() + 1;
vector<vector<int>> dp(m, vector<int>(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<vector>
#include<iostream>
using namespace std;
int CutFe(vector<int>p, int n) {
vector<int>C(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()+1
C[i] = max(C[i], C[j] + p[i - j]);
}
}
return C[n];
}
int main() {
vector<int> p = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 24 };
cout << CutFe(p, 10);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/130515.html
