邮局问题(2) 状态选择 心表示在前个村庄建立个邮局的最 mp]n]就是最后的结果 ■状态选择是动态规划最重要的步骤,也 设w为从第到第个村庄间设立一个邮局 是难点,需要在实践中体会状态选择的 技巧 m[10]= w[10](1<=D m[00]= min(m[i-1(k]+ wk+1D ■可能可以选择不同的状态,导致算法复 其中-1<=k<=j1 杂度不同 ■即找出一个划分点k,第个邮局安排在k+1 ■如果可以尽早知道某些状态是无用的 个村庄安排-1个邮局,总 距离最少。 就可以提高程序的效率,并且节省空间 状态选择 时间与空间的权衡 ■对于背包问题 本质上说动态规划是用空间换取时间的 每新增一件物品f[j[v]总是只与fi 算法 1]u]相关,即f-2][u]的状态已经没有用 可以扔掉。 ■记录中间节点状态就是为了不做重新计 ■对于最长上升子序列问题 算,但这增加了空间的消耗 ■当内存不足时可能需要用时间换回空间 使用D[]状态代替F[状态实际上是我 们保留了最佳状态而扔掉了不够好的状 这时候可能需要考虑哪些状态是常用的 状态予以保留,不常用的状态抛弃 学习动态规划的方法 ■多思考 例题为什么这样选择状态,是怎样列出方 蠢刻态废好的 检验自己是否 ■不明白的时候多查资料 google, baidu ■《算法导论》是入门的好书4 邮局问题（2） „ 假设m[i][j]表示在前j个村庄建立i个邮局的最 小距离和，m[p][n]就是最后的结果 „ 设w[i][j]为从第i到第j 个村庄间设立一个邮局 需要的最小距离 „ m[1][j] = w[1][j] (1 <= j) „ m[i][j] = min(m[i-1][k] + w[k+1][j]) 其中i-1 <= k <= j-1 „ 即找出一个划分点k，第i个邮局安排在k+1与j 之间，从第1到第k个村庄安排i-1个邮局，总的 距离最少。 状态选择 „ 状态选择是动态规划最重要的步骤，也 是难点，需要在实践中体会状态选择的 技巧 „ 可能可以选择不同的状态，导致算法复 杂度不同 „ 如果可以尽早知道某些状态是无用的， 就可以提高程序的效率，并且节省空间 状态选择 „ 对于背包问题 每新增一件物品f[i][v]总是只与f[i- 1][u]相关，即f[i-2][u]的状态已经没有用 了，可以扔掉。 „ 对于最长上升子序列问题 使用D[]状态代替F[]状态实际上是我 们保留了最佳状态而扔掉了不够好的状 态 时间与空间的权衡 „ 本质上说动态规划是用空间换取时间的 算法 „ 记录中间节点状态就是为了不做重新计 算，但这增加了空间的消耗 „ 当内存不足时可能需要用时间换回空间 这时候可能需要考虑哪些状态是常用的 状态予以保留，不常用的状态抛弃 学习动态规划的方法 „ 多思考 思考例题为什么这样选择状态，是怎样列出方 程的 „ 多动手 把动态规划方程变成程序是一个检验自己是否 真的理解动态规划思想的很好的过程 „ 不明白的时候多查资料 google，baidu „ 《算法导论》是入门的好书