動態(tài)規(guī)劃是算法知識很重要的一個(gè)部分，規(guī)律性很強(qiáng)但相對復(fù)雜，讓我們慢慢來感悟。

Best Time to Buy and Sell Stock（121）

題目的要求是只經(jīng)過一次買賣，達(dá)到利益的最大化，操作的對象是個(gè)順序的數(shù)組，因此該題目也是對數(shù)組進(jìn)行操作。
首先，本題目滿足最優(yōu)化理論且無后效性，因此該題目就可以使用動態(tài)規(guī)劃進(jìn)行求解。然后我們發(fā)現(xiàn)我們關(guān)注的是profit，直白地說我們要找的是數(shù)組中不連續(xù)的前后兩個(gè)數(shù)的最大差（后-前）。所以在遍歷數(shù)組的時(shí)候要記錄price_max, price_min。當(dāng)遇到now_price大于price_max的時(shí)候，我們要更新profit,price_max；當(dāng)遇到now_price小于price_min的時(shí)候，我們要更新price_min,price_max，不需要算profit。遍歷結(jié)束我們也會得到相應(yīng)的結(jié)果。
具體代碼如下：

def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    
    if len(prices) < 2: return 0
    profit, price_max, price_min = 0, prices[0], prices[0]
    
    for now_price in prices[1:]:
        if now_price > price_max:
            price_max = max(price_max, now_price)
            profit = max(profit, (price_max-price_min))
        if now_price < price_min:
            price_min = min(price_min, now_price)
            price_max = price_min
    return profit

House Robber(198)

這是一道非常非常典型的動態(tài)規(guī)劃題目(DP)，題目的大概意思就是有一條筆直的街道，每一個(gè)house里都有給定的錢數(shù)讓作為搶匪的我們?nèi)ツ米撸绻谕煌硗盗讼噜彽膬杉?，那么警察就會抓人了（聽起來還蠻有趣）。將題目進(jìn)行抽象其實(shí)就是在一個(gè)數(shù)組中找一個(gè)不相鄰的集合，加和的結(jié)果最大化。
我們的求解主體方式：當(dāng)我選定要偷第n棟house的時(shí)候，那么我們算上之前偷的，最大值就是nums[n]+max(have_stolen[n-2],have_stolen[n-3])。如果-1，就會報(bào)警；如果-4，那么have_stolen[n-2]一定大于等于have_stolen[n-4]的值。代碼如下：

def rob(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    rob = [0,0,0]
    for pre_house,money in enumerate(nums): 
        rob.append(money+max(rob[pre_house],rob[pre_house+1]))
    return max(rob[-1],rob[-2])

House Robber(213)

延續(xù)上一個(gè)題目的思路，我只需要通過兩次遍歷就可以得到結(jié)果，一次是刪去最后一家，一次是刪去第一家。經(jīng)過調(diào)整后的代碼如下：

def rob(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) == 0 : return 0
    if len(nums) == 1 : return nums[0]
    rob1 = [0,0,0]
    result = 0
    for pre_house,money in enumerate(nums[:-1]): 
        rob1.append(money+max(rob1[pre_house],rob1[pre_house+1]))
    rob2 = [0,0,0]
    for pre_house,money in enumerate(nums[1:]): 
        rob2.append(money+max(rob2[pre_house],rob2[pre_house+1]))
    return max(rob1[-1],rob1[-2],rob2[-1],rob2[-2])

Range Sum Query - Immutable(303)

這道題目真的不用強(qiáng)行站隊(duì)DP，因?yàn)檫^于簡單，所以直接上代碼（python的自帶函數(shù)大家一定要慢慢積累使用喲）

def __init__(self, nums):
    """
    initialize your data structure here.
    :type nums: List[int]
    """
    self.origin_nums = nums

def sumRange(self, i, j):
    """
    sum of elements nums[i..j], inclusive.
    :type i: int
    :type j: int
    :rtype: int
    """
    return sum(self.origin_nums[i:j+1])

然而劇情就這么反轉(zhuǎn)了，時(shí)間超了什么鬼。。。。所以我們還是用DP把加工過的數(shù)據(jù)存到數(shù)組當(dāng)中比較好。

def __init__(self, nums):
    """
    initialize your data structure here.
    :type nums: List[int]
    """
    self.nums = nums + [0]
    for i in xrange(len(self.nums)-2, -1, -1): self.nums[i] += self.nums[i+1]
def sumRange(self, i, j):
    """
    sum of elements nums[i..j], inclusive.
    :type i: int
    :type j: int
    :rtype: int
    """
    return self.nums[i] - self.nums[j+1]

在這里我還是要說一下代碼并不是很好：首先是我們改動了原數(shù)組，然后就是對i和j越界的問題并沒有考慮，既然沒有報(bào)錯(cuò)，那就先放在這里，以后加工（不要相信程序員的“to do list” LoL）

Range Sum Query 2D - Immutable(304)

延續(xù)303題目的思路，代碼呈現(xiàn)如下：

def __init__(self, matrix):
    """
    initialize your data structure here.
    :type matrix: List[List[int]]
    """
    self.matrix = matrix
    for row in range(len(matrix)):
        self.matrix[row] += [0]
        for col in xrange(len(matrix[0])-2,-1,-1):
            self.matrix[row][col]+=self.matrix[row][col+1]

def sumRegion(self, row1, col1, row2, col2):
    """
    sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
    :type row1: int
    :type col1: int
    :type row2: int
    :type col2: int
    :rtype: int
    """
    result = 0
    for row in self.matrix[row1:row2+1]: result = result + row[col1] - row[col2+1]
    return result

Counting Bits(338)

題目的大概問題就是求取一個(gè)十進(jìn)制數(shù)轉(zhuǎn)化成二進(jìn)制，會有幾個(gè)一。要把從0到這個(gè)數(shù)所有的十進(jìn)制數(shù)都做統(tǒng)計(jì)，并在一個(gè)數(shù)組中顯示出來。所以我們就要找規(guī)律。

0～0
1～1
2～3 1 2
4～7 1 2 2 3
8～15 1 2 2 3 2 3 3 4

因此，我們不難發(fā)現(xiàn)我們以2的N次方為分割單位，例如：4～7，就是將0～3統(tǒng)計(jì)的每一個(gè)數(shù)+1；也就是說，num = 3-->[0,1,1,2]，num = 7-->[0,1,1,2]+[1,2,2,3]。思路理清好，我們就會以簡短的代碼將答案呈現(xiàn)出來：

def countBits(self, num):
    """
    :type num: int
    :rtype: List[int]
    """
    result,count= [0],1
    while num > 0:
        if num >= count: result = result + [x+1 for x in result]
        else:result = result + [x+1 for x in result[:num-count]]
        num -= count
        count*=2
    return result

未完待續(xù)。。。。