推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

动态规划中的坐标压缩:离散化与稀疏状态处理.docx

更新时间:2026-10-13 20:12:33 大小:39K 上传用户:江岚查看TA发布的资源 标签:动态规划坐标压缩离散化稀疏状态状态空间压缩 下载积分:2分 评价赚积分 (如何评价?) 打赏 收藏 评论(0) 举报

资料介绍

动态规划中的坐标压缩:离散化与稀疏状态处理

动态规划的某些问题中,状态取值可能很大或分散(如坐标范围 ),直接开数组会内存超限。**坐标压缩(离散化)**把分散的取值映射到连续的较小范围,从而压缩状态空间。它是处理"大范围稀疏取值"DP的关键技巧。

坐标压缩的概念

坐标压缩(Coordinate Compression / Discretization):把原本取值范围大、且取值分散的一组值,映射为连续的 ( 为不同取值的个数)。

例如坐标范围 ,但实际只用到  这几个值,压缩后映射为 (按大小排序后重编号)。

  c
// 坐标压缩:把离散值映射到连续小范围
vector<int> vals;   // 所有出现的取值
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());   // 去重
// 原始值x映射到:lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1
int compress(int x) {
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
}

坐标压缩在DP中的应用

坐标压缩常用于DP中"值域很大但实际取值少"的场景。


部分文件列表

文件名 大小
动态规划中的坐标压缩:离散化与稀疏状态处理.docx 39K

全部评论(0)

暂无评论

上传资源 上传优质资源有赏金

  • 打赏
  • 30日榜单

推荐下载