一:基本思想 与分治法类似,其基本思想也是将待求问题分解为若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,DP求解的问题,经分解得到的子问题往往不是互相独立的。 二:解题步骤 1):分析一个最优解决方案应该具备的结构 2):递归定义最优解决方案 3):由底至上构建一个最优解决方案 三:经典题目 1:最长公共子序列LCS:已知两个数列S1和S2,长度分别为m和n,求最长公共子序列的长度和序列 设c[i,j]=LCS{S1[1…i],S2[1…j]},则c[m,n]=LCS{S1,S2},注意到 {c[i-1,n-1]+1 S1[i]=S2[j]...