【算法】动态规划
动态规划（一）
动态规划（Dynamic Programming）其实是运筹学中一种优化方法，动态规划一般就是求最值，比如最少次数、最短距离等。
求解动态规划的核心问题其实就是 穷举。因为要求出问题的最值，所以需要穷举出每一种答案找到最值。
当存在重复子问题时，如果是暴力穷举就会重复计算，导致效率低下。而优化的方法是建立“备忘录”或“DP数组”，避免重复计算。
例题：凑零钱问题
现有 k种面额的硬币，面值分别 c1,c2,...,ck，每种硬币的数量是无限的，现在有一个目标金额 amount，问最少需要多少枚硬币可以凑到这个金额，如果凑不出就返回 -1。
假如现有 k=3，面额为 1,2,5的三种硬币，目标金额 amount = 11，则最少需要3枚硬币凑出，即 5 + 5 + 1 = 11。
子问题
子问题是原问题的划分，例如求f(8)需要求出f(7)，求f(7)需要求出f(6)以此类推，f(8)的子问题是f(7)，f(7)的子问题是f(6)。
凑零钱问题中，求目标 11最少硬币数量，子问题就是 10最少硬币数量，再次划分就是 9最少硬币数量以此类推。
最优子结构
首先这是一个的动态规划问题，因为它具有“最优子结构”。“最优子结构”的子问题间必须相互独立、互不干扰。
比如：a = b + c，求a的最大值就需要求b和c的最大值，b和c互不干扰，因此这符合“最优子结构”。如果b与c互相干扰，比如增长b那么c就减小，那么就不是“最优子结构”。
凑零钱的问题中，各硬币的数量之间没有限制，硬币总数也是无限的。子问题之间是相互独立的。
状态转移
动态规划的核心是穷举最值，只有列举出正确的“状态转移方程”才能正确穷举。
思考确定状态转移方程：
- 确定 base case（最简情况）。在凑零钱中当
amount=0时就返回0，表示不需要硬币了。 - 确定“状态”，也是原问题和子问题的变量。因为硬币是无限的，硬币的面额也是确定的，当目标不断向base case靠近，所以唯一的“状态”就是目标
amount。 - 确定“选择”，也就是导致“状态”产生“变化”的行为。目标
amount之所以会变，是因为“选择”了硬币。当选择了面额为1的硬币，那么目标amount=11就变为了amount=10，所以硬币的面额就是选择。 - 明确dp函数/数组的定义。接下来会先展示递归，所以使用dp函数，dp函数中参数就是状态转移的变量，也就是“状态”，函数返回值就是计算的量。
一、暴力递归解法
这道题中当目标金额为0 时，所需要的硬币为0；小于0时，无解，返回 -1。 状态转移方程：
代码：
//coins为硬币面额，amount为目标金额//coins=[1,2,5]，amount=11func dp(coins []int,amount int)int{ if n==0 {return 0} // base case if n<0 {return -1} num:=amount+1 //因为凑出硬币的数量永远也不可能大于目标金额，所以amount+1表示无穷大。而求最小值，所以初始化无穷大。 //“选择” for _,coin:=range coins{ sub:=dp(coins,amount - coin) if sub == -1{continue} //子问题无解，跳过 //min() if num > 1+sub{ num = 1+sub } } if num==amount+1{ //没有凑出 return -1 } return num}递归树：
通过递归树可以看到，存在 amount相同的重复子问题，从而导致算法效率低下。
递归算法时间复杂度 = 子问题总数时间复杂度 x 每个子问题时间复杂度
在此暴力递归中，子问题总数时间复杂度为，每个子问题时间复杂度为。因此本暴力递归的中时间复杂度为。
二、带“备忘录”的递归解法
从上述的暴力递归树中可以看出，存在许多重复的子问题，这些重复的子问题就是导致算法效率低的主要原因。那么针对这个问题，我们可以建立一个“备忘录”来存储每个子问题计算的结果，在计算子问题之前先查询是有结果存在“备忘录”中，如果存在就直接使用“备忘录”中的值而不再去计算。
一般“备忘录”可以使用数组或哈希表来建立。
代码：
var tab []int //备忘录func dp(coins []int,amount int)int{ //初始化备忘录 if tab == nil{tab=make([]int,len(coins))}
if n==0 {return 0} if n<0 {return -1} num:=amount+1 for _,coin:=range coins{ i := amount - coin //查表，若结果不存在的话就进行计算 if tab[i]==0{ tab[i] = dp(coins,i) } if tab[i] == -1{continue} //min() if num > 1 + tab[i]{ num = 1 + tab[i] } } if num==amount+1{ return -1 } return num}带有“备忘录”的递归就解决了重复子问题冗余的问题,因此子问题的个数不会超过目标金额，因此带“备忘录”的递归的总时间复杂度为。
三、dp数组迭代解法
以上递归都是自顶向下的解法，“状态”amount的变化为：11、10、…、0
而dp数组迭代则是自底向上的解法，“状态”amount的变化为：1、2、…、11
dp数组的定义：当目标金额为 n时，最多需要 dp[n]枚硬币。
代码：
func coinChange(coins []int,amount int)int{ //创建dp数组，长度为amount+1 dp := make([]int,amount+1)
//初始化dp数组，除dp[0]以外都赋值amount+1 //以dp数组下标为各“状态”目标金额。 //当“状态”为0时，结果为零，因此dp[0]=0。base case //除0其他以外，都赋值amount+1。amount+1为硬币永远也达不到的数量，本题求最少硬币数量，因此amount+1表示无穷大。 for i:=1;i<amount+1;i++{ dp[i] = amount+1 } //变量所有状态取值 for i:=0;i<len(dp);i++{ //寻找最少硬币数量 for _,coin := range coins{ // 子问题无解，跳过 if i-coin<0 { continue } //min() if dp[i] > 1+dp[i-coin]{ dp[i] = 1+dp[i-coin] } } } //结果为amount+1“无穷大”为无解返回-1 if dp[amount] == amount+1{ return -1 } return dp[amount]}支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或打赏支持！
加载更多…