动态规划概念、特点、经典例题和于其它算法思想的比较

2024-06-10 03:10| 来源: 网络整理| 查看: 265

目录 1.动态规划概念2.动态规划适用问题的特点2.1 最优子结构2.2 重复子问题2.3 无后效性 3. 动态规划的例子3.1 简单例子——Fibonacci数列3.2 经典例子——背包问题 4 动态规划解题思路和方法5 动态规划和贪心、回溯、分治算法的比较5.1 动态规划5.2 贪心5.3 回溯5.4 分治

1.动态规划概念

动态规划（Dynamic Programming,DP）是通过把原问题分解成相对简单的子问题的方式来解决复杂问题的方法。它的基本思想是将待求解问题分解成不同部分（即子问题），然后依据子问题的解以得出原问题的解，而子问题又可递归地分解为子子问题（到此跟分治法的思想类似，后面是不同）。通常许多子问题可能会重复出现(重复子问题)，DP试图仅仅解每个子问题一次，在求得每个子问题的解后将其保存起来，下次再需要求解相同子问题时，直接查表得到,从而减少计算量，它的精髓在于记住求过的解来节省时间，体现了以空间换时间的算法思想，这也是其与分治法最大的区别。此外，还看到有资料对DP思路的阐述是将问题分解为多个阶段，每个阶段对应一个决策。我们记录每个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合推导下一个阶段的状态集合，动态地往前推进，直至到达最终阶段，这一阐述和DP的名字更贴合，也指出DP适用的问题是多阶段决策最优解模型。

2.动态规划适用问题的特点 2.1 最优子结构

将母问题分解为子问题后，当子问题最优时，母问题通过优化选择一定最优的情况（或者说成母问题的最优解可由子问题的最优解构建得到）。从状态的角度理解，就是后面阶段的状态可以由前面阶段的状态推导出来。如挖金矿问题中，国王面临的问题可分解成左右大臣需要解决的问题，左大臣要解决的子问题是在不挖第10个矿的情况下，给定挖矿人数，确定在前9个矿中挖取最多金子的方案，右大臣要解决的子问题是在挖第10个矿的情况下，给定挖矿人数，确定在前9个矿中挖取最多金子的方案，当左右大臣给出了各自的最优方案后，国王就可以根据子问题的最优解以及第10个矿的信息确定整体最优解。

2.2 重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生相同的状态。有时子问题是否会重复出现不好分析，也可将母问题和子问题本质上是一样的，只是输入参数不同作为依据。

2.3 无后效性

子问题的解一旦确定，就不再改变，不受它之后包含它的更大问题的求解决策影响

3. 动态规划的例子 3.1 简单例子——Fibonacci数列 #include #include using namespace std; int fib1(int n) {// 递归版 return n < 2 ? n : fib1(n-1) + fib1(n-2); } int fib2(int n, vector &table) {// 动态规划自顶向下的备忘录版，就是在递归版的基础上用一个表去记录已求出的子问题的解 if(table[n] != -1) return table[n]; if(n < 2) table[n] = n; else table[n] = fib2(n-1, table) + fib2(n-2, table); return table[n]; } int fib3(int n) {// 动态规划自底向上迭代版 if(n=0) { cout row = new Array(w+1).fill(false) } function backpackMem(i, cw) { if(cw == w || i==n) { if(cw > maxW) maxW = cw return } if(mem[i][cw]) return mem[i][cw] = true backpackRecur(i+1, cw) // 不选第i个物品 if(cw + weight[i] // 初始化状态表 state[0][0] = true if(weight[0] if(state[i-1][j]) // 不选第i个物品 state[i][j] = state[i-1][j] } for(let j=0; j if(state[n-1][j]) { maxW = j // return // 返回决策序列 let res = [] for(let i=n-1; i>0; --i) { if(j-weight[i] >= 0 && state[i][j] !== state[i-1][j]) { res.unshift(i) j = j-weight[i] } } if(j > 0) res.unshift(0) return res } } } 解法4：动态规划优化空间复杂度 let maxW = -Infinity let weight = [2,2,4,6,3] // 物品重量 let n = 5 // 物品个数 let w = 9 // 背包最大载重 let state = new Array(w+1).fill(false) function backpackDP(i, cw) { // 初始化状态表 state[0] = true if(weight[0] //注意是从后往前的顺序，否则上一轮循环算好的结果可能在被使用前被覆盖掉 if(state[j]) // 选第i个物品 state[j+weight[i]] = state[j] } } for(let j=w; j>=0; j--) { if(state[j]) { maxW = j return } } } 带价值的升级版0-1背包问题

对于一组不同重量、不同价值、不可分割的物品，选择一些装入包中，在满足背包最大重量限制情况下，背包中物品总价值的最大值是多少？

解法1：回溯（递归） let maxVal = -Infinity let weight = [2,2,4,6,3] // 物品重量 let value = [3,4,8,9,6] let n = 5 // 物品个数 let w = 9 // 背包最大载重 /* @param: i——物品索引 @param: cw——决策完第i个物品后的背包重量 @param: cv——决策完第i个物品后的背包价值 */ function backpackRecur(i, cw, cv) { if(cw==w || i==n) { if(cv > maxVal) maxVal = cv return } backpackRecur(i+1, cw, cv) // 不选第i个物品 if(cw+weight[i] mem[i] = new Array(w+1).fill(-1) // mem[i][j]表示用i+1个物品组成重量不超过j的组合所具有的最大价值 } // 状态转移方程为f(i, j) = max(f(i-1, j), f(i-1, j-weight[i])+value[i]), j>=weight[i];f(i, j) = f(i-1, j), j state[i] = new Array(w+1).fill(-1) // state[i][j]表示用i+1个物品组成重量不超过j的组合所具有的最大价值 } function backpackDP() { // 初始化状态 state[0][0] = 0 // if(weight[0] < w) // state[0][weight[0]] = value[0] for(let j=weight[0]; j // if(state[i-1][j] != -1) // 不选第i个物品 // state[i][j] = state[i-1][j] // } // for(let j=0; j if(j if(state[n-1][j] > maxVal) { maxVal = state[n-1][j] return maxVal } } } 解法4：动态规划优化空间复杂度 let maxVal = -1 let weight = [2,2,4,6,3] // 物品重量 let value = [3,4,8,9,6] let n = 5 // 物品个数 let w = 9 // 背包最大载重 let state = new Array(w+1).fill(-1) function backpackDP() { // 初始化状态 state[0] = 0 // if(weight[0] < w) // state[weight[0]] = value[0] for(let j=weight[0]; j // if(state[j] != -1) {// 选第i个物品 // let tmp = state[j] + value[i] // if(tmp > state[j+weight[i]]) // state[j+weight[i]] = tmp // } state[j] = Math.max(state[j], state[j-weigth[i]]+value[i]) } } for(let j=w; j>=0; --j) { if(state[j] > maxVal) { maxVal = state[j] return maxVal } } } 4 动态规划解题思路和方法

从前面的例子中可以看出，求解动态规划问题的思路是定义状态并写出状态转移方程，然后可以采用自顶向下的递归+备忘录方法或者自底向上的填写状态转移表方法。

对于递归+备忘录的方法，注意根据状态转移方程寻找边界条件作为递归终止条件，比如状态转移方程中下标索引的边界值

对于填写状态转移表方法，也要注意状态转移表的初始化

5 动态规划和贪心、回溯、分治算法的比较 5.1 动态规划核心思想：将问题分解成多个阶段，记录各阶段可达的状态集合，通过当前阶段的状态集合推导下一阶段的状态集合，动态向前推进，空间换时间适用问题：多阶段决策最优解问题算法特点：最优子结构、无后效性、重复子问题经典应用：斐波那契数列、背包问题 5.2 贪心核心思想：只走一次，每一步都选择当前对自己最优的决策适用问题：多阶段决策最优解问题，更具体来说是针对定义了限制值和期望值的一组数据，从中选出几个数据，在满足限制值的情况下期望值最大，如纸币找零、限重背包价值最大问题算法特点：最优子结构、无后效性、贪心选择性（通过局部最优的选择能产生全局最优）经典应用：霍夫曼编码、区间覆盖 5.3 回溯核心思想：穷举搜索比较并且可回退适用问题：适用范围很广但时间复杂度是指数级的算法特点：适用广，复杂度高经典应用：深度优先搜索 5.4 分治核心思想：分而治之再合并结果适用问题：也较为广泛算法特点：子问题结构相似但不重叠经典应用：二分搜索、MapReduce

参考资料：

动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

【本文地址】

公司简介

联系我们