上下界数位dp

张开发
• 2026/4/20 9:35:09 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

上下界数位dp
lc3906数位DP逐位填数每位都有 [lo, hi] 的上下界约束同时可以有“额外要求”。路径上的位必须非递减当前值 ≥ 上一个路径位的值需要记录 pre 状态。统计强大整数最后 len(s) 位必须完全等于 s 的对应数字只需判断当前位置是否属于后缀区域若是则填固定值。这类本质上就是增加状态或条件来限制枚举范围class Solution {public:long long countGoodIntegersOnPath(long long l, long long r, string directions){string low_s to_string(l);string high_s to_string(r);int n high_s.size();int diff_lh n - low_s.size();vectorarraylong long, 10 memo(n);vectorint8_t in_path(n);int pos n - 16;// 右下角是下标 n-1那么左上角是下标 n-16for (char d : directions) {if (pos 0) {// 只需要对网格图的后 n 个格子做标记in_path[pos] true;// 标记在路径中的格子}pos d R ? 1 : 4;// 往下相当于往右数 4 个位置}in_path[n - 1] true;// 终点一定在路径中auto dfs [](this auto dfs, int i, int pre, bool limit_low, bool limit_high) - long long {if (i n) // 成功到达终点return 1; // 找到了一个好整数if (!limit_low !limit_high memo[i][pre] 0)return memo[i][pre] - 1; // 见下面注释int lo limit_low i diff_lh ? low_s[i - diff_lh] - 0 : 0;int hi limit_high ? high_s[i] - 0 : 9;long long res 0;// 如果当前位置在路径中那么当前位置填的数必须 preint start in_path[i] ? max(lo, pre) : lo;for (int d start; d hi; d) {res dfs(i 1, in_path[i] ? d : pre, limit_low d lo, limit_high d hi);}if (!limit_low !limit_high) {memo[i][pre] res 1;// 记忆化的时候多加一这样 memo[i][j] 就不需要初始化成 -1}return res;};return dfs(0, 0, true, true);}};

更多文章