算法提高之LeetCode刷题it数据结构和算法分析

Dynamic Programming-动态规划(偶尔更新)

2017-05-24  本文已影响139人  Nick_Zuo

（欢迎转载，但请注明出处并附带链接）
算法好久没复习了，今天看见一妹子在办公室刷Leetcode，顿时我也来了兴趣，也准备刷着玩。仔细想想以前学算法时，或多或少都有些遗漏或不足，借着这次机会都补上。
先从动态规划下手吧，记得当初在这个算法上挣扎了很久。本文先理论后实践

动态规划(DP)

该算法的核心价值就两部分：描述状态 和 推导状态的演变过程。其余基础概念我不介绍了，网上大牛写的好文多得是。在这就说说自己的感受。
这个核心价值可以解决很多的DP问题，感觉更像是一种泛式( 这里想表达：这是一个一般性的解决方案，如果具体到某一个问题上，都有改进的空间)。很多东西学到最后都是一种思想，只是在某一具体问题上表现形式不同。
到这理论结束，下面来实战，就围绕这个核心价值转

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]

上面代码还有改进空间，正如本人之前说的"这是一个一般性的解决方案，如果具体到某一个问题上，都有改进的空间"

// 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 更新

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
  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 更新

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 更新

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), 比之前那个快了不少~~

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]

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

上一篇下一篇

猜你喜欢

热点阅读