动态规划解决从数组 b 中选择下标的问题
题目描述
给你一个大小为 4 的整数数组 a 和一个大小至少为 4 的整数数组 b。你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并且要求满足 i0 < i1 < i2 < i3。你的得分将是：
a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]
你需要返回你能够获得的最大得分。
思路分析
这道题可以通过动态规划（DP）来解决。我们定义 dp[i][j] 表示从数组 b 的前 i 个元素中，选择 j 个元素可以获得的最大得分。核心思路是，对于每个元素 b[i]，我们可以选择使用或不使用它，更新状态转移方程。
状态转移方程
- 如果我们选择使用
b[i-1]，那么我们可以用它更新dp[i][j]为dp[i-1][j-1] + b[i-1] * a[j-1]。 - 如果不使用
b[i-1]，则dp[i][j] = dp[i-1][j]。
我们从这两个选择中选出最大的值。
动态规划实现
typedef long long LL;
class Solution {
public:
long long maxScore(vector<int>& a, vector<int>& b) {
int n = b.size();
// dp[i][j] 表示从前 i 个 b 中选择 j 个元素的最大得分
vector<vector<LL>> dp(n+1,vector<LL>(5,0)); // 5 是因为 a 的大小是 4
// 初始化，不能从0个元素中选择1到4个数，故赋值为最小值
for(int i = 1; i <= 4; i++) {
dp[0][i] = INT_MIN;
}
// 遍历数组 b 的每个元素
for(int i = 1; i <= n; i++) {
// j 表示已经选了多少个元素
for(int j = 1; j <= 4; j++) {
// 如果选择 b[i-1]，则得分更新为 dp[i-1][j-1] + b[i-1] * a[j-1]
// 如果不选择 b[i-1]，保持之前的最大得分 dp[i-1][j]
dp[i][j] = max(dp[i-1][j-1] + (LL)b[i-1] * a[j-1], dp[i-1][j]);
}
}
// 最终答案是从 b 中选择 4 个元素的最大得分
return dp[n][4];
}
};
时间复杂度分析
- 外层循环遍历数组
b，时间复杂度为O(n)。 - 内层循环最多进行 4 次，时间复杂度为
O(4)。 - 总的时间复杂度为
O(n)，空间复杂度为O(n)。
总结
这道题目通过动态规划有效解决了在不违反顺序条件下，选择数组元素的最大得分问题。动态规划的状态转移方程简单明了，通过合理的初始化和选择过程，最终可以得到最优解。
解题思路
这道题的核心是找到 target 中的每一段，可以由 words 的前缀组成的子字符串，且要找到最少的组合来拼接完整个 target。为此，使用 Trie 树 来快速匹配 words 中的前缀，同时用 动态规划 来求解最少的前缀组合数。
主要步骤
-
构建 Trie 树：用 Trie 树来存储所有
words的前缀，这样我们可以高效地在target中查找每个位置开始的最长有效前缀。 -
动态规划状态定义：
dp[i]表示能够组成target[0:i)的最少前缀数量。这里target[0:i)是一个左闭右开区间，代表target从第 0 个字符到第 i-1 个字符。- 初始状态为
dp[0] = 0，表示空字符串可以用 0 个前缀组成。
-
转移过程：
- 对于每个位置
i，我们通过查询 Trie 树来获取从target[i]开始的所有有效前缀，假设这些前缀的长度分别为len1, len2,...。那么我们更新dp[i + len]，使得：dp[i + len] = min(dp[i + len], dp[i] + 1) - 每次在
target上从当前位置尝试所有可能的前缀，并更新dp。
- 对于每个位置
-
终止条件：
- 如果我们无法构成某个位置，即
dp[i] == INT_MAX，说明target无法用前缀构成，直接返回 -1。 - 否则，最后返回
dp[n]，即target[0:n)的最少前缀数量。
- 如果我们无法构成某个位置，即
代码实现
class Solution {
public:
static const int N = 1e5 + 10; // Trie 树的最大节点数
int son[N][26], idx; // son 用于表示 Trie 树的每个节点，26 表示字母 a-z，idx 为 Trie 树的节点索引
// 插入一个字符串到 Trie 树中
void insert(string s) {
int p = 0; // 从根节点开始
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (son[p][c - 'a'] == -1) // 如果当前节点不存在子节点
son[p][c - 'a'] = ++idx; // 创建新节点
p = son[p][c - 'a']; // 转移到子节点
}
}
// 查询以 pos 开始的 target 的所有有效前缀长度
vector<int> query(string s, int pos) {
int p = 0; // 从根节点开始
vector<int> res;
for (int i = pos; i < s.size(); i++) {
char c = s[i];
if (son[p][c - 'a'] == -1) return res; // 如果 Trie 中没有匹配的前缀，直接返回
p = son[p][c - 'a']; // 向下走 Trie
res.push_back(i - pos + 1); // 记录前缀的长度
}
return res; // 返回所有以 pos 开始的有效前缀长度
}
int minValidStrings(vector<string>& words, string target) {
memset(son, -1, sizeof son); // 初始化 Trie 树
for (auto word : words) insert(word); // 将所有 words 插入 Trie
int n = target.size();
vector<int> dp(n + 1, INT_MAX); // dp[i] 表示组成 target[0:i) 的最少前缀数量
dp[0] = 0; // 初始状态，空字符串需要 0 个前缀
// 动态规划求解最少前缀数
for (int i = 0; i < n; i++) {
if (dp[i] == INT_MAX) // 如果当前位置不可达，直接返回 -1
return -1;
auto v = query(target, i); // 查询从 i 开始的所有前缀
for (auto c : v) {
dp[i + c] = min(dp[i + c], dp[i] + 1); // 更新 dp 值
if (dp[n] != INT_MAX) return dp[n]; // 如果已经能构成 target，提前返回结果
}
}
return dp[n] == INT_MAX ? -1 : dp[n]; // 如果 dp[n] 仍然为 INT_MAX，说明无法构成 target
}
};