leetcode :
no_62:
思路：
本題暴力遞歸去遍歷所有情況會超時
如果發(fā)現(xiàn) result（m，n） = result(m-1,n) + result(m,n-1) 這個特征式子就好做了
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = []
for i in range(n):
dp.append([])
for j in range(m):
dp[i].append(0)
for i in range(m):
dp[0][i] = 1
for i in range(n):
dp[i][0] = 1
for i in range(1,n):
for j in range(1,m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
no_121:
思路：類似游標毕源，以一個start來記錄假定的買入亮隙，單次循環(huán)撕彤，通過判定當前股票價格與假定的買入價格的大小來修改start灰嫉，如果當前值小于start處的值节仿，更新start巢块，假定在此處買入；如果當前的值大于start處的值护桦，得出一個假定的收益量含衔，存入benifit中，最終去benifit中取max就是最大的利益
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == []:
return 0
benifit = []
start = 0
for i in range(len(prices)):
if prices[i] - prices[start] < 0:
start = i
benifit.append(0)
else:
benifit.append(prices[i] - prices[start])
return max(benifit)
no_122:
思路：因為沒有任何限制調價二庵，那么把所有的上漲都納入收益那就是那就是最大收益
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == []:
return 0
# start = 0
allBenifit = 0
for i in range(len(prices)):
if i!=0:
if prices[i] > prices[i-1]:
allBenifit+=(prices[i]-prices[i-1])
return allBenifit
no_123:
思路： 動態(tài)規(guī)劃的思想贪染。dp表示最大收益量，應該有三個維度：
第一個維度記錄天數(shù)催享，第二個維度記錄當前是否持有股票杭隙，第三個維度記錄當前已經賣出股票的次數(shù)。狀態(tài)轉移方程如代碼所示因妙，最終的最大值應該滿足（最后一天痰憎，手上不持有股票，已經完成一次或者兩次交易攀涵，不小于0） 等幾個條件铣耘。注意邊界值。
class Solution(object):
def maxProfit(self, prices):
if prices == []:
return 0
dp = [[[0,0,0],[0,0,0]] for i in range(len(prices))]
dp[0][0][0] = 0
dp[0][1][0] = - prices[0]
for item in dp[0]:
for j in range(len(item)):
if j > 0 :
item[j] = float('-inf')
for i in range(1,len(prices)):
dp[i][0][0] = 0
dp[i][0][1] = max (dp[i-1][1][0] + prices[i] , dp[i-1][0][1])
dp[i][0][2] = max(dp[i-1][1][1] + prices[i],dp[i-1][0][2])
dp[i][1][0] = max(dp[i-1][0][0] - prices[i],dp[i-1][1][0])
dp[i][1][1] = max(dp[i-1][0][1] - prices[i],dp[i-1][1][1])
dp[i][1][2] = float('-inf')
return max(0,dp[len(prices)-1][0][1],dp[len(prices)-1][0][2])
no_188: 買賣股票的最佳時機 4
思路：
這個也可以用類似于上一提的三維dp來做以故，區(qū)別在于最后一個維度應該時k+1維的蜗细，表示賣出了0次 - k次。
問題：會超出空間限制。
解決：把 k > len(prices) / /2 的情況拎出來討論炉媒，此時交易次數(shù)足夠大踪区，用第122題的方法去解決即可。
class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
def noK(prices):
start = 0
allBenifit = 0
for i in range(len(prices)):
if i!=0:
if prices[i] > prices[i-1]:
allBenifit+=(prices[i]-prices[i-1])
return allBenifit
if prices == []:
return 0
if len(prices) == 1:
return 0
if k > len(prices) // 2:
return noK(prices)
dp = [[[0 for j in range(k+1)] for i in range(2)]for i in range(len(prices))]
dp[0][0][0] = 0
dp[0][1][0] = -prices[0]
for item in dp[0]:
for j in range(len(item)):
if j>0:
item[j] = float('-inf')
for i in range(1,len(prices)):
dp[i][0][0] = 0
dp[i][1][k] = float('-inf')
for j in range(k+1):
if j>0:
dp[i][0][j] = max(dp[i-1][1][j-1] + prices[i],dp[i-1][0][j])
if j<k:
dp[i][1][j] = max(dp[i-1][0][j] - prices[i] , dp[i-1][1][j])
return max(0,max(dp[len(prices)-1][0]))
no_309:
dp是一個二維的吊骤，第一個維度表示天數(shù)缎岗，第二個維度表示狀態(tài)，有三個狀態(tài)：1 手上沒有股票白粉，2 手上有股票 3 冷凍期
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == [] :
return 0
dp = [[0,0,0] for i in range(len(prices))]
dp[0][0] = -prices[0] # 第一天有股票
dp[0][2] = 0
dp[0][1] = 0
for i in range(1,len(prices)):
dp[i][0] = max(dp[i-1][2] - prices[i] , dp[i-1][0])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][1], dp[i-1][2])
return max(dp[len(prices)-1][1],dp[len(prices)-1][2],0)
no_714:
跟前面的題類似的密强，出售時記得減去 fee 就行了
class Solution(object):
def maxProfit(self, prices, fee):
"""
:type prices: List[int]
:type fee: int
:rtype: int
"""
if prices == []:
return 0
dp = [[0,0] for i in range(len(prices))]
# dp[天數(shù)][0：手上無股票，1：手上有股票]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,len(prices)):
dp[i][0] = max(dp[i-1][1] + prices[i] - fee , dp[i-1][0])
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i])
return max(0,dp[len(prices)-1][0])
這周的leetcode題目很多涉及動態(tài)規(guī)劃蜗元，感覺比前面兩周的難了不少。
聽課筆記：
去網上找了吳恩達老師的課后編程練習系冗。跟著敲了 邏輯回歸 和 單層神經網絡 的代碼奕扣，去理解代碼邏輯。
發(fā)現(xiàn)有些相關知識掌握不夠掌敬，如numpy以及matplotlib.pyplot惯豆，去學了一些numpy的用法，并做了相關筆記
http://www.reibang.com/p/a5c8882864af
