算法分析与设计编程题 动态规划
矩阵连乘
题目描述
解题代码
void printOptimalParens(vector<vector<int>>& partition, int i, int j) {
if (i == j) cout << "A" << i; // 单个矩阵，无需划分
else {
cout << "(";
printOptimalParens(partition, i, partition[i][j]);
printOptimalParens(partition, partition[i][j] + 1, j);
cout << ")";
}
}
// nums[i]: nums[0]为矩阵A1的行数，nums[i](i >= 1)表示矩阵Ai的列数
// 如输入为 nums = { 30,35,15,5,10,20,25 }，代表矩阵行列数如下：
// A1: 30 * 35, A2: 35 * 15, A3: 15 * 5, A4: 5 * 10, A5: 10 * 20, A6: 20 * 25
int matrixChainOrder(vector<int>& nums) {
int n = nums.size() - 1;
// dp[i][j]表示矩阵链A[i～j]的最优解
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT32_MAX));
// partition[i][j]表示矩阵链A[i～j]最优解对应的划分k
vector<vector<int>> partition(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; ++i) {
dp[i][i] = 0; // 矩阵链长度为1时，最优解为0
}
for (int len = 2; len <= n; ++len) { // len为矩阵链长度
for (int i = 1; i + len - 1 <= n; ++i) { // 矩阵链左端点i
int j = i + len - 1; // 矩阵链右端点j
for (int k = i; k <= j - 1; ++k) { // 划分点k
int sum = dp[i][k] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j];
if (sum < dp[i][j]) { // 更新最优解
dp[i][j] = sum;
partition[i][j] = k;
}
}
}
}
printOptimalParens(partition, 1, n); // 打印最优方案
return dp[1][n];
}最长公共子序列
题目描述
解题代码
void printLCS(const string& text1, vector<vector<char>>& dir, int i, int j) {
if (i == 0 || j == 0) return;
if (dir[i][j] == 'S') { // 向左上移动
printLCS(text1, dir, i - 1, j - 1);
cout << text1[i - 1]; // 递归后再输出字符，以实现反向
}
else if (dir[i][j] == 'U') { // 向上移动
printLCS(text1, dir, i - 1, j);
}
else { // 向左移动
printLCS(text1, dir, i, j - 1);
}
}
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
// dp[i][j]表示text1[0～i-1]和text2[0～i-1]的LCS
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// dir[i][j]记录得到LCS的移动方向，以便构造最优解
vector<vector<char>> dir(m + 1, vector<char>(n + 1, '*'));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
dir[i][j] = 'S';
}
else if (dp[i - 1][j] >= dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
dir[i][j] = 'U';
}
else {
dp[i][j] = dp[i][j - 1];
dir[i][j] = 'L';
}
}
}
printLCS(text1, dir, m, n); // 构造最优解
return dp[m][n];
}最大子段和
题目描述
解题代码
分治法
int dividedMaxSubSum(vector<int>& nums, int left, int right) {
if (left == right) return nums[left]; // 单个元素最大子段和为该元素的值
int mid = left + (right - left) / 2;
int lSum = dividedMaxSubSum(nums, left, mid); // 划分左端子数组的最大子段和
int rSum = dividedMaxSubSum(nums, mid + 1, right); // 划分右端子数组的最大子段和
// 计算穿过划分点的子数组左端的最大子段和
int midL = 0, maxMidL = INT32_MIN;
for (int i = mid; i >= left; --i) {
midL += nums[i];
maxMidL = max(maxMidL, midL);
}
// 计算穿过划分点的子数组右端的最大子段和
int midR = 0, maxMidR = INT32_MIN;
for (int i = mid + 1; i <= right; ++i) {
midR += nums[i];
maxMidR = max(maxMidR, midR);
}
// 子数组的最大子段和为三者之间最大的一个
return max(maxMidL + maxMidR, max(lSum, rSum));
}
int maxSubSum(vector<int>& nums) {
int n = nums.size();
return dividedMaxSubSum(nums, 0, n - 1);
}动态规划
int maxSubSum(vector<int>& nums) {
int res = 0, sum = 0;
for (int i = 0; i < nums.size(); ++i) {
if (sum > 0) {
sum += nums[i];
}
// 当前累计总和小于零，则包含该部分的子段必不可能为最大子段，可根据反证法证明：
// 假设子段S为最大子段，且其包含总和为负的前缀子段s1，则将该前缀子段删去后得到的新子段S'的子段和必定大于S，与假设矛盾
else {
sum = nums[i];
}
res = max(res, sum);
}
return res;
}凸多边形最优三角剖分
题目描述
解题代码
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 3; len <= n; ++len) { // 多边形顶点序列长度len
for (int i = 0; i + len - 1 < n; ++i) { // 顶点序列左端点i
int j = i + len - 1; // 顶点序列右端点j
dp[i][j] = INT32_MAX;
for (int k = i + 1; k < j; ++k) { // 划分点k
int cost = dp[i][k] + dp[k][j] + values[i] * values[j] * values[k];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}0-1背包问题
题目描述
解题代码
int knapsack01(vector<int>& weights, vector<int>& values, int c) {
int n = weights.size();
// dp[i][j]表示可选商品为0～i，背包容量为j情况下的最优解
vector<vector<int>> dp(n, vector<int>(c + 1, 0));
for (int j = weights[0]; j <= c; ++j) {
// 若i=0，即可选商品只有0，此时最优解为：能否装下商品0 ? values[0] : 0
dp[0][j] = values[0];
}
for (int i = 1; i < n; ++i) { // 可选商品0～i
for (int j = 1; j <= c; ++j) { // 背包容量j
dp[i][j] = dp[i - 1][j]; // 不选择商品i
if (j >= weights[i]) { // 若j >= weight[i]，则可选择商品i
// 取两种情况（选择或不选择商品i）下的最优解
dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i]] + values[i]);
}
}
}
return dp[n - 1][c];
}最优二叉搜索树
题目描述
解题代码
// pNonLeaves[i](i >= 1)表示非叶结点i的搜索概率，pLeaves[i](i >= 0)表示叶子结点i的搜索概率
// 如输入为 pNonLeaves = { 0.0,0.15,0.10,0.05,0.10,0.20 }
// 表示非叶结点i的搜索概率p[1～5] = [ 0.15,0.10,0.05,0.10,0.20 ]（原数组首个0为占位用，无实际含义）
// 如输入为 pLeaves = { 0.05,0.10,0.05,0.05,0.05,0.10 }
// 表示非叶结点i的搜索概率q[0～5] = [ 0.05,0.10,0.05,0.05,0.05,0.10 ]
double optimalBST(vector<double>& pNonLeaves, vector<double>& pLeaves) {
int n = pNonLeaves.size() - 1; // 非叶节点的个数n
// dp[i][j]表示根据结点序列pNonLeaves[i～j]和pLeaves[i～j]构成的最优解（子树）
// dp[i][i-1]代表只含有叶结点i-1的子树（不含非叶节点）
vector<vector<double>> dp(n + 2, vector<double>(n + 1, DBL_MAX));
// root[i][j]表示dp[i][j]对应的子树的根节点，可根据其构造最优二叉搜索树
vector<vector<int>> root(n + 1, vector<int>(n + 1));
// pSum[i][j]表示结点序列pNonLeaves[i～j]和pLeaves[i～j]的概率总和
vector<vector<double>> pSum(n + 2, vector<double>(n + 1));
for (int i = 1; i <= n + 1; ++i) { // 初始化dp和pSum
dp[i][i - 1] = pLeaves[i - 1];
pSum[i][i - 1] = pLeaves[i - 1];
}
for (int len = 1; len <= n; ++len) { // 结点序列长度len
for (int i = 1; i + len - 1 <= n; ++i) { // 序列左端点i
int j = i + len - 1; // 序列右端点j
pSum[i][j] = pSum[i][j - 1] + pNonLeaves[j] + pLeaves[j]; // 递推计算结点序列区间概率和
for (int r = i; r <= j; ++r) { // 将非叶结点r选作根节点
double cost = dp[i][r - 1] + dp[r + 1][j] + pSum[i][j]; // 该情况下的搜索代价
if (cost < dp[i][j]) { // 更新最优解
dp[i][j] = cost;
root[i][j] = r;
}
}
}
}
return dp[1][n];
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Lordaeron_ESZ's blog！
微信
支付宝
相关推荐
评论
