【算法总结】动态规划
2020-12-13 02:22
标签：ext 关于 AMM 迭代 优化方法 公式 整型 ali hellip 动态规划（DP：Dynamic Programming） 动态规划是求解包含重复子问题的最优化方法，把原问题分解为相对简单的子问题。动态规划只能应用于有最优子结构的问题（即局部最优解能决定全局最优解，或问题能分解成子问题来求解）。 基本思想 将原问题分解为相似的子问题，再合并子问题的解以得出原问题的解。 动态规划在求解的过程中通过保存子问题的解求出原问题的解（而不是简单地分而治之），仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。 动态规划 = 记忆化搜索 分治与动态规划 共同点：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解. 不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。 动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。 问题特征 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。 递推求解问题就是最简单的一类动规问题，状态转移方程就是递推方程。 动规解题的一般思路 1.将原问题分解为子问题 2.确定状态 3.确定状态转移方程 典型问题 01最长递增子序列 问题： 设L=是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=，其中k1 解题思路（1）：找子问题 背包问题 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 最终总结 学习历程：枚举-->搜索（系统化）-->动态规划（记忆化） 搜索的实现 方式1：递归-剪枝 方式2：动态规划 目的： 方法： 具体使用哪种方式？依情况而定 【算法总结】动态规划 标签：ext 关于 AMM 迭代 优化方法 公式 整型 ali hellip 原文地址：https://www.cnblogs.com/yun-an/p/11032975.html