春秋招如同达摩克里斯之剑，逼着我又捡起来这些乱七八糟的算法书。
这里分享一些关于动态规划的一些学习笔记。
动态规划(Dynamic Programming)其实一开始是在优化理论出现的，他不是计算机里的东西，但是他却在计算机里扮演了一个非常重要的角色，是无论如何也绕不开的一种算法。
回想一下，我们学过的很多算法，其实都是应用条件给的非常详细的，比如Dijkstra算法，要求你在一个无负权无环路的无向图上使用，最后返回一个包含着最短路径的顶点的数组。又比如什么快速排序，要求你有一个数组，以及定义在这个数组上一个大小关系，最后返回一个排序好的数组给你。
但是动态规划实际上不是单单一种算法，如果非要找个类比对象，那么动态规划实际上就是跟“递归”，“分治算法”，这两个词一样，形容的是一大类算法。
首先说一下什么叫做最优化问题，口头一点的话，最优化问题就是让你求在给定条件下一个函数的最大值最小值或者极值。一个无负权无环路的无向图，求某个点到某个点的最长，最短路径，就是可以归类成最优化问题。再举个例子，求最长公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。
想要使用动态规划，那么问题就非得是一个最优化问题不可。而且这还不够，问题必须是适用于最优性原理的优化问题。而最优性原理，通俗一点，就是这个问题本身和他的子问题有递推公式。和分治这种算法不一样的是，动态规划主要用来决策。
有了递推公式还不够，拿fibonacci数列来说，如果你像下面这样求解问题，那么复杂度大概是O(2^n)
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
fibonacci(n-1) 展开后的式子和 fibonacci(n-2)展开后的式子基本上都是重复计算，比方说我们展开等式右边第一个 fibonacci(n-1) = fibonacci(n-2) + fibonacci(n-3)。这里出现一个fibonacci(n-2) 但是原来的式子也有一个fibonacci(n-2)，这里两个fibonacci(n-2)在不知道对方存在的情况下会分别展开出一堆，明显是重复计算了，所以我们现在想最好只算一次fibonacci(n-2)。
那么怎么办呢，我们引入缓存。然后改变一下计算的顺序。
fibo[0] = 1
fibo[1] = 1
for (int i=2;i<=n;i++)
fibo[i] = fibo[i-1] + fibo[i-2];
我们把fibonacci计算出来的值存入一个叫做fibo的数组(缓存)里。然后改变了一下计算顺序，我们原来是fibonacci(n)一直展开到fibonacci(1)然后再返回。现在我们先算fibonacci[2] 再算fibonacci[3]。 等等。
废话了一堆，以上大概就是动态规划的简介。来看看例题吧。
我们现在有一个数字三角形。每个位置有一个数字，到达后即可获得累加，求从最顶端到达最低层能达到的最大数字和。
这显然是一个最优化问题，关键在于，看不出这个问题能有什么子问题，以及如果有子问题，那么又和这个问题本身有什么关系，适用不适用于最优性原理。这应该是解决动态问题最难的地方。找出递推关系，或者叫做状态转移方程。
我们把最顶端的点设为(1,1)，第二行第一个叫做(2,1)，以此类推。第i行第j个就叫做(i,j)，往左下角走就(i+1,j) 右下角走就(i+1,j+1) 。
数字三角形
设dp[i][j] 为 从(i,j)到最低层走的最大值，那么子问题就是dp[i+1][j] 和 dp[i+1][j+1]。我们现在要探索dp[i][j] 和 dp[i+1][j]以及dp[i+1][j+1]的关系。
不难得出dp[i][j] = max(dp[i+1][j] , dp[i+1][j+1]) + (i,j)上的值。
我们可以很轻松地得到如图所示的最低层的dp值，dp[5][1] = 12 , dp[5][2] = 7，那么dp [4][1] = max(dp[5][1] + dp[5][2] ) + val(i,j) = 12 + 6 = 18。
事实上还有很多题目看起来一点也不像是适用于最优性原理的优化问题，但是通过人为地引进状态，可以变成动态规划问题。比如DAG上的动态规划，就是一个非常常用的动态规划模型。
网友评论