国外算法设计与分析课件12

《国外算法设计与分析课件12》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、DynamicProgrammingCopyrightLiZimao@2007-2008-1SCUECExpectedOutcomesStudentsshouldbeabletoWritedownthefourstepsofdynamicprogrammingComputeaFibonaccinumberandthebinomialcoefficientsbydynamicprogrammingComputethelongestcommonsubsequenceandtheshortestcommonsupersequenceoftwogivensequencesbyd

2、ynamicprogrammingSolvetheinvestproblembydynamicprogrammingCopyrightLiZimao@2007-2008-1SCUECDynamicProgrammingDynamicProgrammingisageneralalgorithmdesigntechnique.InventedbyAmericanmathematicianRichardBellmaninthe1950stosolveoptimizationproblemsMainidea:solveseveralsmaller(overlapping)sub

3、problemsrecordsolutionsinatablesothateachsubproblemisonlysolvedoncefinalstateofthetablewillbe(orcontain)solutionDynamicprogrammingvs.divide-and-conquerpartitionaproblemintooverlappingsubproblemsandindependentonesstoreandnotstoresolutionstosubproblemsCopyrightLiZimao@2007-2008-1SCUECFrame

4、ofDynamicProgrammingProblemsolvedSolutioncanbeexpressedinarecursivewaySub-problemsoccurrepeatedlySubsequenceofoptimalsolutionisanoptimalsolutiontothesub-problemFrameCharacterizethestructureofanoptimalsolutionRecursivelydefinethevalueofanoptimalsolutionComputethevalueofanoptimalsolutionina

5、bottom-upfashionConstructanoptimalsolutionfromcomputedinformationCopyrightLiZimao@2007-2008-1SCUECThreebasiccomponentsThedevelopmentofadynamicprogrammingalgorithmhasthreebasiccomponents:Arecurrencerelation(fordefiningthevalue/costofanoptimalsolution);Atabularcomputation(forcomputingtheva

6、lueofanoptimalsolution);Abacktracingprocedure(fordeliveringanoptimalsolution).CopyrightLiZimao@2007-2008-1SCUECExample:FibonaccinumbersRecalldefinitionofFibonaccinumbers:f(0)=0f(1)=1f(n)=f(n-1)+f(n-2)ComputingthenthFibonaccinumberrecursively(top-down):f(n)f(n-1)+f(n-2)f(n-2)+f(n-3)f(n-3)

7、+f(n-4)...CopyrightLiZimao@2007-2008-1SCUECExample:FibonaccinumbersComputingthenthfibonaccinumberusingbottom-upiteration:f(0)=0f(1)=1f(2)=0+1=1f(3)=1+1=2f(4)=1+2=3f(5)=2+3=5f(n-2)=f(n-1)=f(n)=f(n-1)+f(n-2)ALGORITHMFib(n)F[0]0,F[1]1fori2tondoF[i]F[i-1]+F[i-2]ret