- 1
- 2
- 3
- 4
- 5
动态规划中的合并类DP模型与代价设计.docx
资料介绍
动态规划中的合并类DP：合并石子与决策代价
合并类DP处理"把若干元素合并成更大结构"的问题，前文已介绍石子合并、矩阵链乘等。本文深入合并类DP的通用模型：状态、转移、代价函数的设计，以及如何把"合并代价"正确建模。理解合并类DP的核心，是处理这类问题的关键。
合并类DP的通用模型
合并类DP把相邻元素（或区间）合并成更大结构，状态 
表示"合并区间 的最优代价"，转移枚举最后一步合并的分割点 ：
c
// 合并类DP通用框架
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,k,j));
}
代价函数 是每类问题的关键差异。
合并代价的设计
不同合并问题的差异主要在代价函数：
石子合并：cost = 区间石子总数（前缀和）。矩阵链乘：cost = 三维维度乘积。最优BST：cost = 区间频率和。
部分文件列表
| 文件名 | 大小 |
| 动态规划中的合并类DP模型与代价设计.docx | 38K |
最新上传
- 打赏
- 30日榜单
-
21ic小能手 打赏3.00元 10小时前
资料：小米MIX3电路图
-
21ic小能手 打赏10.00元 11小时前
-
21ic小能手 打赏5.00元 11小时前
-
江岚 打赏100.00元 2天前
用户：潇潇江南
-
他山之石可攻玉 打赏50.00元 2天前
用户：烟雨
-
21ic下载 打赏1.00元 2天前
用户：王小琪
-
yahuang001 打赏3.00元 3天前
-
yahuang001 打赏1.00元 3天前
-
zhongshaoxiong 打赏3.00元 3天前
-
他山之石可攻玉 打赏60.00元 3天前
用户：烟雨
-
江岚 打赏210.00元 3天前
用户：潇潇江南
-
江岚 打赏100.00元 3天前
-
21ic下载 打赏310.00元 3天前
用户：gsy幸运
-
21ic下载 打赏310.00元 3天前
用户：zhengdai
-
21ic下载 打赏310.00元 3天前
用户：江岚
-
21ic下载 打赏210.00元 3天前
用户：潇潇江南
-
21ic下载 打赏60.00元 3天前
用户：他山之石可攻玉
-
21ic下载 打赏60.00元 3天前
用户：烟雨
-
21ic下载 打赏60.00元 3天前
用户：w178191520
-
21ic下载 打赏60.00元 3天前
用户：w993263495
-
21ic下载 打赏110.00元 3天前
用户：xzxbybd
-
21ic下载 打赏60.00元 3天前
用户：zq_1943
-
21ic下载 打赏20.00元 3天前
用户：kk1957135547
-
21ic下载 打赏20.00元 3天前
用户：sun2152
-
21ic下载 打赏20.00元 3天前
用户：铁蛋锅
-
21ic下载 打赏20.00元 3天前
用户：xuzhen1
-
21ic下载 打赏20.00元 3天前
用户：w1966891335
-
21ic下载 打赏35.00元 3天前
用户：有理想666
-
21ic下载 打赏15.00元 3天前
用户：nuaanuaa111
-
21ic下载 打赏20.00元 3天前
用户：liqiang9090
-
21ic下载 打赏15.00元 3天前
用户：ningmengge
-
21ic下载 打赏10.00元 3天前
用户：mulanhk
-
21ic下载 打赏5.00元 3天前
用户：asys
-
21ic下载 打赏10.00元 3天前
用户：舞蹈荀彧
-
21ic小能手 打赏5.00元 3天前
资料：磁编码器开源方案
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
江岚 打赏20.00元 3天前
-
江岚 打赏50.00元 3天前
-
江岚 打赏20.00元 3天前
全部评论(0)