lc3469记忆化class Solution {public:int minCost(vectorint nums) {int n nums.size();vector memo(n - 1, vectorint(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埃氏筛dijkconst int MX 10000;bool np[MX];int init [] {np[1] true;// 埃氏筛标记每个数是否为合数或者 1for (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();vectorint dis(pow(10, len_n), INT_MAX);dis[n] n;priority_queuepairint, int, vectorpairint, 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;}};