lc3469
记忆化
class Solution {
public:
int minCost(vector<int>& nums) {
int n = nums.size();
vector memo(n - 1, vector<int>(n - 1));
auto dfs = [&](this auto&& dfs, int i, int j) -> int {
if (i == n)
return nums[j];
if (i == n - 1)
return max(nums[j], nums[i]);
int& res = memo[i][j];
// 注意这里是引用
if (res == 0) { // 没有计算过
int a = nums[j], b = nums[i], c = nums[i + 1];
res = min({dfs(i + 2, j) + max(b, c),
dfs(i + 2, i) + max(a, c),
dfs(i + 2, i + 1) + max(a, b)});
}
return res;
};
return dfs(1, 0);
}
};
lc3444
埃氏筛+dijk
const int MX = 10000;
bool np[MX];
int init = [] {
np[1] = true;
// 埃氏筛，标记每个数是否为合数（或者 1）
for (int i = 2; i < MX; i++) {
if (!np[i]) {
for (int j = i * i; j < MX; j += i) {
np[j] = true; // 合数
}
}
}
return 0;
}();
class Solution {
public:
int minOperations(int n, int m) {
if (!np[n] || !np[m]) {
return -1;
}
int len_n = to_string(n).length();
vector<int> dis(pow(10, len_n), INT_MAX);
dis[n] = n;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(n, n);
while (!pq.empty()) {
auto [dix_x, x] = pq.top();
pq.pop();
if (x == m) {
return dix_x;
}
if (dix_x > dis[x]) {
continue;
}
int pow10 = 1;
for (int v = x; v; v /= 10) {
int d = v % 10;
if (d > 0) { // 减少
int y = x - pow10;
int new_d = dix_x + y;
if (np[y] && new_d < dis[y]) {
dis[y] = new_d;
pq.emplace(new_d, y);
}
}
if (d < 9) { // 增加
int y = x + pow10;
int new_d = dix_x + y;
if (np[y] && new_d < dis[y]) {
dis[y] = new_d;
pq.emplace(new_d, y);
}
}
pow10 *= 10;
}
}
return -1;
}
};
