首页 > 代码库 > 动态规划初学
动态规划初学
数字三角形：
定义状态（i,j）：表示当前所处位置
定义指标函数 d(i,j) ：表示从格子(i,j)出发能得到的最大和
找到状态转移方程： d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}
总状态为O(n^2),每个状态决策为O(1),总的时间复杂度为O(n^2)。
方法：直接递归
缺点：重复计算过多
优化：记忆化搜索
或者： 递推计算（关键 边界和计算顺序）
DAG
嵌套三角形：
定义状态(i,j)：表示矩形的二元关系，为了通过图来建模？
PS：(i)表示从结点i出发遍历能到达的结点
定义指标函数d(i)：表示从结点i出发的最长路长度
找到状态转移方程：d(i)=max{ d(j)+1 | (i,j)属于E}
PS：矩形之间关系通过图建模表示出来，定义状态为从i点出发的最长路径，这是一个最优子结构。通过状态转移方程找出全局最优与局部最优的关系。
总状态为O(n),每个决策有O(n)，时间复杂度为O(n^2)。
注意：因为起始点不定，有n种可能。
硬币问题：
定义状态(i)：表示S减去v[n]之后还剩的硬币数额
定义指标函数d(i)：表示剩余硬币额为i时最大最小硬币数
找到状态转移方程：d(i)=max{ d(S-v[i])+1, d(i) }
d(i)=min{ d(S-v[i])+1, d(i) }
总状态为O(S),每个状态的决策为O(n),时间复杂度为O(Sn)。
城市里的间谍(uva1025)
定义状态(i,j)：表示所处时刻和所在车站号
定义指标函数d(i,j)：表示等待的最短时间
找到状态转移方程：d(i,j)=min{ d(i,j), d(i+time[j],j+1) }当有向右开的车时
d(i,j)=min{ d(i,j), d(i+1,j)+1}没车等一分钟
d(i,j)=min{ d(i,j), d(i+time[j-1],j-1) }当有向左开的车时
状态有：O(nT),每个状态至多有3个决策，因此总的时间复杂度为O(nT)。
巴比伦塔(uva437)
定义状态(idx,k)：表示所选立方体的编号和高度编号（因为用长宽作为数组可能太大且浪费空间太多）
定义指标函数d(idx,k)：表示所选立方体总高度最大
找到状态转移方程：d(idx,k) =max{ d(idj)+blocks[idx][k] | (idx,k,idj,h)属于E}
状态总数为O(n),每个状态决策有O(n)个，时间复杂度为O(n^2)。
注意：因为起点不定，建立图表。如嵌套三角形。
旅行(uva1347) 与数字三角形相似
定义状态(i,j)：表示两个人所处位置编号
定义指标函数d(i,j)：表示走过1,2,...max(i,j)所有点，剩下的距离
找到状态转移方程：d(i,j)=min{ d(i+1,j),d(i+1,i) }
边界：d(n-1, j) = dist(n-1, n) + dist(j, n) (1 ≤ j < n-1)
最终所求答案就是dist(1, 2) + d(1, 2)
状态有：O(n^2),每个状态决策为O(1)，总时间复杂度为O(n^2)。
动态规划初学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。