算法设计与分析作业02

3-1

解： 采用动态规划算法。

1. 定义子问题：
   我们将原问题分割为更小的子问题：一个子序列中最长严格递增列的长度。

2. 构建动态规划数组：
   使用一个数组 $dp$ 来存储以每个元素为结尾的最长递增子序列的长度。$dp[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列的长度。初始时每个位置都设置为 1（每个元素自身可以作为一个长度为 1 的子序列）。

3. 状态转移方程：
   对于每个元素 $nums[i]$（从第二个元素开始），我们需要检查它之前的所有元素 $nums[j]$（$j < i$）。
   如果 $nums[i] > nums[j]$，则可以将 $nums[i]$ 加入以 $nums[j]$ 为结尾的子序列中，因此我们更新 $dp[i]$ 为 $dp[j] + 1$ 的最大值：

   $$$$

   $$$$

   $dp$数组中的最大值即为所求。

根据上述过程，算法的时间复杂度为$O(n^2)$

代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {
		int n = nums.size();
		if (n == 0) 
			return 0;
		vector<int> dp(n, 1);
		for (int i = 1; i < n; i++)
			for (int j = 0; j < i; j++)
				if (nums[i] > nums[j])
					dp[i] = max(dp[i], dp[j] + 1);
		int res = 1;
		for (int i = 0; i < n; i++)
			res = max(res, dp[i]);
		return res;
	}
};

int main() {
	vector<int> nums = {1,3,6,7,9,4,10,5,6};
	Solution sol;
	cout << sol.lengthOfLIS(nums) << endl;
	return 0;
}

运行结果

3-3

解： 采用动态规划算法。

1. 定义子问题：
   将原问题分割为更小的子问题：计算出前 $j$ 个单词的最小排版花费。

2. 构建动态规划数组：
   用数组 $c[j]$ 表示从第 $1$ 个单词到第 $j$ 个单词的最小花费。构建矩阵 $extras[i][j]$ 表示将单词 $i$ 到 $j$ 放在同一行时的剩余空格数；用矩阵 $lc[i][j]$ 表示将单词 $i$ 到 $j$ 放在同一行时的空格花费（多余空格数的立方）。

3. 状态转移方程：
   对于每一个位置 $j$，我们需要检查前面所有的可能断行位置 $i$，并计算在第 $i$ 到 $j$ 的单词放在同一行的最小花费。使用如下递推公式来更新 $c[j]$：

   $$c[j] = \min_{1 \leq i \leq j} \{c[i - 1] + lc[i-1][j-1]\}$$

   其中，$c[i-1]$ 表示前 $i-1$ 个单词的最小花费，$lc[i-1][j-1]$ 表示将单词 $i$ 到 $j$ 放在同一行的立方空格花费。

4. 返回最终结果：
   $c[N]$ 表示前 $N$ 个单词的最小花费，即为所求的最小排版花费。

根据上述过程，建立extras和lc矩阵的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$；求解 $c[N]$的时间复杂度为 $O(nM)$，其中 $M$ 是一行可以容纳的字符数，空间复杂度为 $O(n)$。

代码

定义类

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
	int prettyPrint(vector<int>& length, int M) {
		int N = length.size();  // 单词的数量
		
		// extras[i][j] 表示将单词 i 到 j 放在一行时的多余空格数
		vector<vector<int>> extras(N, vector<int>(N, 0));
		
		// lc[i][j] 表示将单词 i 到 j 放在一行时的花费 (立方空格数)
		vector<vector<int>> lc(N, vector<int>(N, 0));
		
		// c[j] 表示前 j 个单词的最小花费
		vector<int> c(N + 1, INT_MAX);
		
		// 计算 extras 矩阵
		for (int i = 0; i < N; i++) {
			extras[i][i] = M - length[i];  // 只有一个单词在一行
			for (int j = i + 1; j < N; j++) {
				extras[i][j] = extras[i][j - 1] - length[j] - 1;  // 计算多余空格
			}
		}
		
		// 计算 lc 矩阵
		for (int i = 0; i < N; i++) {
			for (int j = i; j < N; j++) {
				if (extras[i][j] < 0) {
					lc[i][j] = INT_MAX;  // 单词超过长度，无法放在一行
				} else if (j == N - 1) {
					lc[i][j] = 0;  // 最后一行不用考虑空格
				} else {
					lc[i][j] = extras[i][j] * extras[i][j] * extras[i][j];  // 花费为多余空格数的立方
				}
			}
		}
		
		// 计算最优的 c 数组
		c[0] = 0;  // 初始状态，没有单词时花费为0
		for (int j = 1; j <= N; j++) {
			for (int i = 1; i <= j; i++) {
				if (c[i - 1] != INT_MAX && lc[i - 1][j - 1] != INT_MAX) {
					c[j] = min(c[j], c[i - 1] + lc[i - 1][j - 1]);
				}
			}
		}
		
		return c[N];  // 返回最终最小花费
	}
};

主函数

int main() {
	Solution sol;
	vector<int> lengths = {3, 2, 2, 5};  // 每个单词的长度
	int M = 6;  // 每行最多容纳的字符数
	cout << "Minimum cost: " << sol.prettyPrint(lengths, M) << endl;
	return 0;
}

运行结果