小李飛刀：做題第九彈！
寫在前面的話
感覺做題越多遇到的寫法越多，有種躍躍欲試的感覺~
認真做題
第一題
難度：簡單
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數。
我的題解：
class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ old = 1 new = 1 for i in range(2,n+1): old,new = new,new+old return newv
我的思路：
這題是一個標準的 動態規劃 的題目，第二步所需要的步數其實是基於第一步，第三步則基於第二步。
用筆計算就可以看出，有一定的規律，新的一步的最優解等於前面一步的最優解+之前所有步數的最優解。
不過可能還沒有抓到動態規劃的真諦，總覺得哪裡需要再校正下思路。
第二題
難度：簡單
給定字串 J 代表石頭中寶石的型別，和字串 S 代表你擁有的石頭。 S 中每個字元代表了一種你擁有的石頭的型別，你想知道你擁有的石頭中有多少是寶石。
J 中的字母不重複， J 和 S 中的所有字元都是字母。字母區分大小寫，因此"a"和"A"是不同型別的石頭。
我的題解：
class Solution(object):
def numJewelsInStones(self, J, S):
"""
:type J: str
:type S: str
:rtype: int
"""
num = 0
if not J or not S:
return 0
map = {}
for i in J:
map[i] = 1
for j in S:
if j in map:
num += map[j]
return num
我的思路：
這題用了 hash表 的思路，將 J 裡的每個字母單獨存成雜湊表的一個鍵，且對應的值為1。
這樣當 S 進行搜尋的時候，對應將值相加即可得到結果。
第三題
難度：簡單
實現函式 ToLowerCase()，該函式接收一個字串引數 str，並將該字串中的大寫字母轉換成小寫字母，之後返回新的字串。
我的題解：
class Solution(object):
def toLowerCase(self, str):
"""
:type str: str
:rtype: str
"""
s = list(str)
map = {'A':'a','B':'b','C':'c','D':'d','E':'e','F':'f','G':'g','H':'h','I':'i','J':'j','K':'k','L':'l','M':'m','N':'n','O':'o','P':'p','Q':'q','R':'r','S':'s','T':'t','U':'u','V':'v','W':'w','X':'x','Y':'y','Z':'z'}
for i in range(len(s)):
if s[i] in map:
s[i] = map[s[i]]
s1=''.join(s)
return s1
我的思路：
這題....大概寫法非常土了....emmm
認真的寫了個字典，然後對應的寫一下，效率也還可以，但是隻能用於數量少的情況下，還可以看下有沒有其他的寫法。
第四題
難度：中等
我的題解：
class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ dp = [[0 for _ in range(m)] for _ in range(n)] #建立二維陣列 for i in range(n): for j in range(m): if i ==0 or j ==0: dp[i][j] = 1 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1]
我的思路：
非常粗暴的畫了網格圖，然後發現了規律，
dp[i][j] = dp[i-1][j] + dp[i][j-1] ,
和少棉在討論的時候，非常真摯的為了為什麼他知道需要是左邊的值加上上方的值，
給的說法是 最優解的目標就是從左上角到該位置的最優解 ，區域性最優再到全域性最優。
這題也是 動態規劃 的題目，目標總是要分解為子問題。
總結
看《演算法圖解》的時候，涉及動態規劃的小結中有這樣的
- 每種動態規劃解決方案都涉及網格。
- 單元格中的值通常就是你要優化的值
- 每個單元格都是一個子問題，因為你需要考慮如何將問題分解為子問題。