（欢迎转载，但请注明出处并附带链接）
算法好久没复习了，今天看见一妹子在办公室刷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

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

1. 可能有人会问“初始化那一行在做什么？”。首先，在任何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]同理
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]

所有的代码都有优化空间，做的题远远比写在简书上的多，不过有些题解释起来太麻烦，就没写进来，以后偶尔还会更！ 不过明天起准备看下其他算法了。
上面这些代码都有优化的空间，各位改着玩吧