动态规划是算法知识很重要的一个部分，规律性很强但相对复杂，让我们慢慢来感悟。
Best Time to Buy and Sell Stock（121）
题目的要求是只经过一次买卖，达到利益的最大化，操作的对象是个顺序的数组，因此该题目也是对数组进行操作。
首先，本题目满足最优化理论且无后效性，因此该题目就可以使用动态规划进行求解。然后我们发现我们关注的是profit，直白地说我们要找的是数组中不连续的前后两个数的最大差（后-前）。所以在遍历数组的时候要记录price_max, price_min。当遇到now_price大于price_max的时候，我们要更新profit,price_max；当遇到now_price小于price_min的时候，我们要更新price_min,price_max，不需要算profit。遍历结束我们也会得到相应的结果。
具体代码如下：
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)
这是一道非常非常典型的动态规划题目(DP)，题目的大概意思就是有一条笔直的街道，每一个house里都有给定的钱数让作为抢匪的我们去拿走，如果在同一晚偷了相邻的两家，那么警察就会抓人了（听起来还蛮有趣）。将题目进行抽象其实就是在一个数组中找一个不相邻的集合，加和的结果最大化。
我们的求解主体方式：当我选定要偷第n栋house的时候，那么我们算上之前偷的，最大值就是nums[n]+max(have_stolen[n-2],have_stolen[n-3])。如果-1，就会报警；如果-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)
延续上一个题目的思路，我只需要通过两次遍历就可以得到结果，一次是删去最后一家，一次是删去第一家。经过调整后的代码如下：
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)
这道题目真的不用强行站队DP，因为过于简单，所以直接上代码（python的自带函数大家一定要慢慢积累使用哟）
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])
然而剧情就这么反转了，时间超了什么鬼。。。。所以我们还是用DP把加工过的数据存到数组当中比较好。
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]
在这里我还是要说一下代码并不是很好：首先是我们改动了原数组，然后就是对i和j越界的问题并没有考虑，既然没有报错，那就先放在这里，以后加工（不要相信程序员的“to do list” LoL）
Range Sum Query 2D - Immutable(304)
延续303题目的思路，代码呈现如下：
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)
题目的大概问题就是求取一个十进制数转化成二进制，会有几个一。要把从0到这个数所有的十进制数都做统计，并在一个数组中显示出来。所以我们就要找规律。
0～0
1～1
2～3 1 2
4～7 1 2 2 3
8～15 1 2 2 3 2 3 3 4
因此，我们不难发现我们以2的N次方为分割单位，例如：4～7，就是将0～3统计的每一个数+1；也就是说，num = 3-->[0,1,1,2]，num = 7-->[0,1,1,2]+[1,2,2,3]。思路理清好，我们就会以简短的代码将答案呈现出来：
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
未完待续。。。。
