（欢迎转载，但请注明出处并附带链接）
算法好久没复习了，今天看见一妹子在办公室刷Leetcode，顿时我也来了兴趣，也准备刷着玩。仔细想想以前学算法时，或多或少都有些遗漏或不足，借着这次机会都补上。
先从动态规划下手吧，记得当初在这个算法上挣扎了很久。本文先理论后实践
动态规划(DP)
该算法的核心价值就两部分：描述状态 和 推导状态的演变过程。其余基础概念我不介绍了，网上大牛写的好文多得是。在这就说说自己的感受。
这个核心价值可以解决很多的DP问题，感觉更像是一种泛式( 这里想表达：这是一个一般性的解决方案，如果具体到某一个问题上，都有改进的空间)。很多东西学到最后都是一种思想，只是在某一具体问题上表现形式不同。
到这理论结束，下面来实战，就围绕这个核心价值转
- 例1 LeetCode 198. House Robber
根据之前所讲，只要找到描述状态和推导状态演变过程就能解决该问题，那么住这里描述状态是什么呢？ 这里其实很简单，只有一种状态(本人采用数组来记录)，因为根据题目的description只需记录抢到当前屋子的最大值就ok，描述状态如下：
res[i]：抢到第 i个屋子时的目前利益最大值
下面就要找推导状态的演变过程。演变过程用文字描述起来太累也不清晰，采用数学公式来说明，如下（图片是自己做的，找个了在线公式编辑器）：
CodeCogsEqn.gif
当i=0时，只有一个房子，为了最大值，怎么可能不抢
当i=1时，就要比较下哪个屋子更值钱，然后再抢
当i>=2时，就要根据题目要求进行下判断了，分为抢和不抢，其中 f(i-1) 就代表不抢，所以最大利益和上一项相同，而另一个就代表抢。在抢和不抢中找出最大值
代码如下（python实现）：
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
# create the statement
res = []
res = range( len(nums) )
# i = 0
res[0] = nums[0]
# i = 1
if len(nums) > 1: res[1] = max( nums[0], nums[1] )
# i >= 2
for i in range( 2, len(nums) ):
res[i] = max( res[i-1], res[i-2] + nums[i] )
return res[-1]
上面代码还有改进空间，正如本人之前说的"这是一个一般性的解决方案，如果具体到某一个问题上，都有改进的空间"
- 例2 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
来，先找描述状态，从题目中能发现3个状态(本人用3个数组来记录)，如下：
buy[i]: 截至到第 i 天的最大值，且第 i 天执行的是buy操作
sell[i]: 截至到第 i 天的最大值，且第 i 天执行的是sell操作
rest[i]: 截至到第 i 天的最大值，且第 i 天执行的是rest操作
下一步就是 推导状态的演变过程。根据题目的逻辑很轻松就能用如下3个演变过程：
设price为第i 天的价格
// buy操作的第i天只有两种可能（**买**和**不买**）
// 不买就是buy[i-1]；买就必须从rest[i-1]状态切换过来，还要再减去当天的价格
buy[i] = max( rest[i-1] - price, buy[i-1] )
// sell操作也是两种可能(**卖**和**不卖**)
// 不卖就是sell[i-1], 卖就从buy[i-1]的状态切换过来，再加上当天价格
sell[i] = max( buy[i-1] + price, sell[i-1] )
// 这个演变过程被简化过了
// 其原型是max(sell[i-1], buy[i-1], rest[i-1]), 因为rest操作什么也不做，所以就从3个状态中找最大值
// 但是根据题意，不能出现{buy, rest, buy}这种不合理得排序，就删除了buy[i-1]
rest[i] = max( sell[i-1], rest[i-1] )
python代码如下:
注意初始化buy[0]和sell[0]，也挺简单的，就不详述了
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) < 2: return 0
buy = [ 0 for _ in range( len(prices) )]
sell = [ 0 for _ in range( len(prices) )]
rest = [ 0 for _ in range( len(prices) )]
buy[0] = -prices[0] # After buy, you should have -prices[0] profit. Be positive!
sell[0] = -sys.maxint - 1 # you can sell before buy, set sell to MIN
for i in range( 1, len(prices) ):
buy[i] = max(rest[i-1]-prices[i], buy[i-1])
sell[i] = max(buy[i-1]+prices[i], sell[i-1])
rest[i] = max(sell[i-1], rest[i-1])
return max( sell[-1], rest[-1] )
5/25/2017 更新
- 例3 LeetCode 486. Predict the Winner
这次描述状态并不是那么直接，分析一下得到如下:
dp(i,j):累加 player1从第 i 个位置到第 j 个位置选择的数值（即每次选值之和），请注意这个累加值并不是整个数组每项叠加，而是根据题意得出来的（player1选择一个，player2再选择一个，一直重复下去。然后将player1每次选值相加得到dp(i,j) ）
其中用一个二维数组表示dp(i,j)，即dp[ i ][ j ]。看待dp[i][j]时，不要把它想成一个下标表示的值，而是把它看成从 i 到 j 的按题意逻辑得到的累加值，这样比较好理解下面的代码，这点很重要！！！
在用数学公式表达下：
dp(i,j) = max( sum(i,j-1) - dp(i,j-1) + nums[j],
sum(i+1,j) - dp(i+1,j) + nums[i] )
简化后，得到：
dp(i,j) = max( sum(i,j) - dp(i,j-1) , sum(i,j) - dp(i+1,j) )
下面找推导状态的演变过程，其实上面那个式子就可以说是演变过程，但对于解题来说很不理想，所以这次从题目分析。
题目想问player1能不能赢，也就是问player1最后的数值是不是大于player2的数值，即player1 - player2 > 0
下面进行一些数学推导（字迹不好看，请注意看思路:-) ）:
公式推导.JPG
到此描述状态和推到演变过程都结束了
下面开始上代码(依旧python，代码之后还有对一些迷茫地方的讲解)：
class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# store the maximum score player1 picking from i to j
dp = [ [0 for _ in range(len(nums))] for _ in range(len(nums))]
# initializing
for i in range( len(nums) ): dp[i][i] = nums[i]
for i in range( 1, len(nums) ):
for j in range( 0, len(nums)-i ):
dp[j][j+i] = max( nums[j+i] - dp[j][j+i-1], nums[j] - dp[j+1][j+i] )
return dp[0][-1] >= 0
- 可能有人会问“初始化那一行在做什么？”。首先，在任何dp问题中，我们都需要初始化某些值（就是那种能从题目中得到的确定值，在动态规划开始之前它们就已经存在了），在这道题目中能确定的只有dp[0][0] = nums[0], dp[1][1] = nums[1], dp[2][2] = nums[2]...等等。dp[0][0]就是开头说的dp(0,0),即从第0个开始到第0个结束所能得到的累加值，这里只有nums[0]这一个值，后面几个dp[1][1],dp[2][2]同理
- 还有人可能问那个双重循环在干什么？。我们要把全部的case列举出来，放张图举个例子（长度为6的数组）:
举例(1).JPG
今天就说到这了
6/5/2017 更新
- 例4 377. Combination Sum IV
先看描述状态，这里很明显需要一个数组来记录当前共有多少种组合，即：
dp[i]: 代表数值 i 一共有多少种组合方式
下面看推导状态的演变过程，这个过程用个举例来说明：
现在有一个array = [1,2,3]当做已知条件，target为4,请问当前的array可以提供多少种组合组成target？可以列出所有组合：
4 = dp[3] + 1
4 = dp[2] + 2
4 = dp[1] + 3
只有以上3种方式组成数字4，所以其组合总数为:
dp[4] = dp[3] + dp[2] + dp[1]
dp[4] = dp[4-1] + dp[4-2] + dp[4-3]
然后推导出公式
dp[target] = dp[ target - nums[0] ] + dp[target-nums[1]] + ……+ dp[target - nums[ nums.length() - 1] ]
dp[target] = sum( dp[ target - nums[i] ] ), 0 <= i < nums.length() 且 target >= nums[i]
上面最后一步就是推导状态的演变过程
接着上代码（python）:
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [ 0 for _ in range(target+1)]
dp[0] = 1
for i in range(target+1):
for j in range( len(nums) ):
if i >= nums[j]:
dp[i] += dp[ i - nums[j] ]
return dp[target]
这道题挺简单的，敢兴趣的可以自己做优化，欢迎交流！
6/6/2017 更新
- 例5 64. Minimum Path Sum
先找描述状态，基本上一眼就能看出来：
dp[i][j]: 记录当前最小步数
推导状态的演变过程，这个也很简单，从题目中就能知道是个2选1问题，要么move down要么move right，从它俩找出最小值, 其公式为：
dp[i][j] = min ( dp[i-1][j], dp[i][j-1] ) + grid[i][j]
python代码:
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid: return
m = len(grid)
n = len(grid[0])
dp = [ [ 0 for _ in range(n)] for _ in range(m) ]
dp[0][0] = grid[0][0]
for i in range(1,n): dp[0][i] = dp[0][i-1] + grid[0][i]
for i in range(1,m): dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
不过上面这个算法实在太笨了，说下优化吧。
从逻辑上就能知道 i 要把整个二维数组走一遍，并且是按顺序一行一行的走，所以我们就用一个一维数组替代二维数组，当这个循环结束时，我们只关心最后一个位置（即右下角的位置），其他的记不记录都不无所谓，优化后的代码如下：
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid: return
m, n = len(grid), len(grid[0])
dp = [ 0 for _ in range(n) ]
dp[0] = grid[0][0]
for i in range(1, n): dp[i] = dp[i-1] + grid[0][i]
for i in range(1, m):
dp[0] += grid[i][0]
for j in range(1, n):
dp[j] = min( dp[j-1], dp[j] ) + grid[i][j]
return dp[-1]
空间复杂度降为 O(n), 比之前那个快了不少~~
- 例6 62. Unique Paths
这题简直和上一题是好基友，不废话了，先找描述状态
dp[]: 走到当前位置共有几种组合
下面是推导状态的演变过程，如果明白上面那题，这题基本上瞬间解决，直接上公式了：
dp[i][j] = dp[i][j-1] + dp[i-1][j],其中 i,j >= 1
python代码:
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [ [0 for _ in range(n)] for _ in range(m) ]
for i in range(n): dp[0][i] = 1
for i in range(m): dp[i][0] = 1
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
所有的代码都有优化空间，做的题远远比写在简书上的多，不过有些题解释起来太麻烦，就没写进来，以后偶尔还会更！ 不过明天起准备看下其他算法了。
上面这些代码都有优化的空间，各位改着玩吧
网友评论