<html xmlns="http://www.w3.org/1999/xhtml"><head><meta charset="utf-8"><meta name="generator" content="pdf2htmlEX"><meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/css/base.min.css"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/css/fancy.min.css"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/7353349/raw.css"><script src="https://csdnimg.cn/release/download_crawler_static/js/compatibility.min.js"></script><script src="https://csdnimg.cn/release/download_crawler_static/js/pdf2htmlEX.min.js"></script><script>try{pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});}catch(e){}</script><title></title></head><body><div id="sidebar" style="display: none"><div id="outline"></div></div><div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/7353349/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x2 h3 y2 ff2 fs1 fc1 sc0 ls0 ws0">第</div><div class="t m0 x3 h3 y3 ff2 fs1 fc2 sc0 ls0 ws0">第</div><div class="t m0 x4 h3 y2 ff2 fs1 fc1 sc0 ls0 ws0">3</div><div class="t m0 x5 h3 y3 ff2 fs1 fc2 sc0 ls0 ws0">3</div><div class="t m0 x6 h3 y2 ff2 fs1 fc1 sc0 ls0 ws0">章</div><div class="t m0 x7 h3 y3 ff2 fs1 fc2 sc0 ls0 ws0">章</div><div class="t m0 x8 h3 y2 ff2 fs1 fc1 sc0 ls0 ws0">动态规划</div><div class="t m0 x9 h3 y3 ff2 fs1 fc2 sc0 ls0 ws0">动态规划</div></div><div class="pi" data-data='{"ctm":[0.000000,-1.337047,1.337047,0.000000,-82.896936,758.105850]}'></div></div></body></html>
<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/7353349/bg2.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 xa h4 y4 ff2 fs2 fc3 sc1 ls1 ws0">学习要点:</div><div class="t m0 xa h5 y5 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">理解动态规划算法的概念。</span></div><div class="t m0 xa h5 y6 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">掌握动态规划算法的基本要素</span></div><div class="t m0 xa h6 y7 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">1</span><span class="ls2">）最优子结构性质</span></span></div><div class="t m0 xa h6 y8 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">2</span><span class="ls2">）重叠子问题性质</span></span></div><div class="t m0 xa h5 y9 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">掌握设计动态规划算法的步骤。</span></div><div class="t m0 xa h6 ya ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff5 fs4 fc0 ls3">(1)<span class="ff4 ls4">找出最优解的性质，并刻划其结构特征。</span></span></div><div class="t m0 xa h6 yb ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff5 fs4 fc0 ls3">(2)<span class="ff4">递归地定义最优值。</span></span></div><div class="t m0 xa h6 yc ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff5 fs4 fc0 ls3">(3)<span class="ff4 ls5">以自底向上的方式计算出最优值。</span></span></div><div class="t m0 xa h6 yd ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff5 fs4 fc0 ls3">(4)<span class="ff4 ls4">根据计算最优值时得到的信息，构造最优解。</span></span></div></div><div class="pi" data-data='{"ctm":[0.000000,-1.337047,1.337047,0.000000,-82.896936,758.105850]}'></div></div>
<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/7353349/bg3.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">3</div><div class="t m0 xb h5 ye ff2 fs4 fc0 sc0 ls0 ws0">通过应用范例学习动态规划算法设计策略：</div><div class="t m0 xb h6 yf ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">1</span><span class="ls3">）矩阵连乘问题</span></span></div><div class="t m0 xb h6 y10 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">2</span><span class="ls2">）最长公共子序列</span></span></div><div class="t m0 xb h6 y11 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">3</span><span class="ls3">）最大子段和</span></span></div><div class="t m0 xb h6 y12 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">4</span><span class="ls5">）凸多边形最优三角剖分</span></span></div><div class="t m0 xb h6 y13 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">5</span><span class="ls3">）多边形游戏</span></span></div><div class="t m0 xb h6 y14 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">6</span><span class="ls6">）图像压缩</span></span></div><div class="t m0 xb h6 y15 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">7</span><span class="ls6">）电路布线</span></span></div><div class="t m0 xb h6 y16 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">8</span><span class="ls3">）流水作业调度</span></span></div><div class="t m0 xb h6 y17 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5">9</span><span class="ls6">）背包问题</span></span></div><div class="t m0 xb h6 y18 ff3 fs3 fc4 sc0 ls0 ws0">•<span class="_ _0"> </span><span class="ff4 fs4 fc0">（<span class="ff5 ls7">10</span>）最优二叉搜索树</span></div></div><div class="pi" data-data='{"ctm":[0.000000,-1.337047,1.337047,0.000000,-82.896936,758.105850]}'></div></div>
<div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/7353349/bg4.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">4</div><div class="t m0 xc h7 y19 ff6 fs5 fc4 sc0 ls0 ws0"><span class="_ _1"> </span><span class="ff7 fs6 fc0">动态规划算法与分治法类似，其基本思想也是将待求解问题分</span></div><div class="t m0 xd h7 y1a ff7 fs6 fc0 sc0 ls0 ws0">解成若干个子问题</div><div class="t m0 xe h8 y1b ff2 fs7 fc1 sc0 ls0 ws0">算法总体思想</div><div class="t m0 xc h8 y1c ff2 fs7 fc5 sc0 ls0 ws0">算法总体思想</div><div class="t m0 xf h9 y1d ff8 fs2 fc0 sc0 ls0 ws0">n</div><div class="t m0 xc ha y1e ff8 fs8 fc0 sc2 ls8 ws0">T(n/2)</div><div class="t m0 x10 ha y1f ff8 fs8 fc0 sc2 ls8 ws0">T(n/2)<span class="_ _2"> </span>T(n/2)<span class="_ _2"> </span>T(n/2)</div><div class="t m0 xa h9 y20 ff8 fs2 fc0 sc0 ls9 ws0">T(n)</div><div class="t m0 x11 h9 y21 ff8 fs2 fc0 sc0 ls0 ws0">=</div></div><div class="pi" data-data='{"ctm":[0.000000,-1.337047,1.337047,0.000000,-82.896936,758.105850]}'></div></div>
<div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/7353349/bg5.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">5</div><div class="t m0 x12 h7 y19 ff6 fs5 fc4 sc0 ls0 ws0"><span class="_ _1"> </span><span class="ff7 fs6 fc0">但是经分解得到的子问题往往不是互相独立的。不同子问题的</span></div><div class="t m0 x13 h7 y1a ff7 fs6 fc0 sc0 ls0 ws0">数目常常只有多项式量级。在用分治法求解时，有些子问题被</div><div class="t m0 x13 h7 y22 ff7 fs6 fc0 sc0 ls0 ws0">重复计算了许多次。</div><div class="t m0 xa h8 y1b ff2 fs7 fc1 sc0 ls0 ws0">算法总体思想</div><div class="t m0 x12 h8 y1c ff2 fs7 fc5 sc0 ls0 ws0">算法总体思想</div><div class="t m0 x14 h9 y1d ff8 fs2 fc0 sc0 ls0 ws0">n</div><div class="t m0 x15 h9 y20 ff8 fs2 fc0 sc0 ls9 ws0">T(n)</div><div class="t m0 x16 h9 y21 ff8 fs2 fc0 sc0 ls0 ws0">=</div><div class="t m0 x17 ha y23 ff8 fs8 fc0 sc0 lsa ws0">n/2</div><div class="t m0 x18 hb y24 ff8 fs3 fc0 sc2 lsb ws0">T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)</div><div class="t m0 x19 ha y23 ff8 fs8 fc0 sc0 lsa ws0">n/2</div><div class="t m0 x1a hb y24 ff8 fs3 fc0 sc2 lsb ws0">T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)</div><div class="t m0 x1b ha y23 ff8 fs8 fc0 sc0 lsa ws0">n/2</div><div class="t m0 x1c hb y24 ff8 fs3 fc0 sc2 lsb ws0">T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)</div><div class="t m0 x1d ha y23 ff8 fs8 fc0 sc0 lsa ws0">n/2</div><div class="t m0 x1e hb y24 ff8 fs3 fc0 sc2 lsb ws0">T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span>T(n/4)<span class="_ _3"></span><span class="ls0">T</span></div><div class="c x1f y25 w2 hc"><div class="t m0 x20 hb y26 ff8 fs3 fc0 sc2 ls0 ws0">(</div></div><div class="t m0 x21 hb y24 ff8 fs3 fc0 sc2 lsc ws0">n/4</div><div class="c x1f y25 w2 hc"><div class="t m0 x22 hb y26 ff8 fs3 fc0 sc2 ls0 ws0">)</div></div></div><div class="pi" data-data='{"ctm":[0.000000,-1.337047,1.337047,0.000000,-82.896936,758.105850]}'></div></div>
算法
