<h1>
Dynamic Programming
</h1>
<h2>
- [O]70. Climbing Stairs
</h2>
<h3>
題目
</h3>
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
**Example**
```
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
```
<h3>
思路
</h3>
可以走到當前步數的方法數=n-2+n-1 的方法數
```python!
class Solution(object):
def climbStairs(self, n):
table=[1,1,2]
for i in range(3,n+1):
table.append(table[i-1]+table[i-2])
return table[n]
"""
:type n: int
:rtype: int
"""
```
---
<h2>
- [Ｏ] 118. Pascal's Triangle
</h2>
<h3>
題目
</h3>
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
**Example**
```
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```
<h3>
思路
</h3>
模擬巴斯卡三角形的計算方式即可。
```python!
class Solution(object):
def generate(self, numRows):
ans=[[1]]
for i in range(2,numRows+1):
row=[]
row.append(1)
for j in range(1,i-1):
row.append(ans[i-2][j-1]+ans[i-2][j])
row.append(1)
ans.append(row)
return ans
"""
:type numRows: int
:rtype: List[List[int]]
"""
```
---
<h2>
- [O] 300. Longest Increasing Subsequence
</h2>
<h3>
題目
</h3>
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
**Example**
```
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```
<h3>
思路
</h3>
每次都去計算index在這個數字之前的數字，從中找出最長的Subarray。
```python!
class Solution(object):
def lengthOfLIS(self, nums):
ans=[]
for i in range(0,len(nums)):
time=1
for j in range(0,i):
if nums[i]>nums[j]:
time=max(time,ans[j]+1)
ans.append(time)
ans.sort()
return ans[-1]
"""
:type nums: List[int]
:rtype: int
"""
```
---
<h2>
- [O] 198. House Robber
</h2>
<h3>
題目
</h3>
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
**Example**
```
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
```
<h3>
思路
</h3>
分兩個table，一個是搶劫 i-th house，一個是不搶 i-th house，搶劫i-th house = 不搶(i-1)-th house+num[i]，不搶 i-th house = max(不搶(i-1)-th house, 搶劫(i-1)-th house)，最後從兩個table找最大的值。
```python!
class Solution(object):
def rob(self, nums):
get=[nums[0]]
abandon=[0]
for i in range(1,len(nums)):
getHouse=abandon[i-1]+nums[i]
abandonHouse=max(get[i-1],abandon[i-1])
get.append(getHouse)
abandon.append(abandonHouse)
return max(get[-1],abandon[-1])
"""
:type nums: List[int]
:rtype: int
"""
```
---
<h2>
- [O]322. Coin Change
</h2>
<h3>
題目
</h3>
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
**Example**
```
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
```
<h3>
思路
</h3>
用table存每種價錢最小的換幣數，算法是每次都減去現在擁有的幣值，查找table，找最小兌幣數。
```python!
class Solution(object):
def coinChange(self, coins, amount):
if amount==0:
return 0
table=[0]*10001
for i in coins:
if i >amount:
continue
table[i]=1
for i in range(1,amount+1):
for j in coins:
if j >amount:
continue
if i-j>0 and table[i-j]>0:
if table[i]!=0:
table[i]=min(table[i],table[i-j]+table[j])
else:
table[i]=table[i-j]+table[j]
if table[amount]==0:
return -1
return table[amount]
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
```
---
<h2>
- [X]72. Edit Distance
</h2>
<h3>
題目
</h3>
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a character
Delete a character
Replace a character
**Example**
```
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
```
<h3>
思路
</h3>
無從下手
<h3>
Discussion
</h3>
table[i][j]表示 word1(1...i)轉換成word2(1....j)所需要的最少步數。
table[i][0]與table[0][j]可以先做處理分別需要i及j步(將i個字轉換為空字串要i步)。
每次計算table[i][j]，可以先檢查word1第i個字及word2第j個字(word1[i-1]== or != word2[j-1]，要記得-1，python從index 0開始計數):
1. 如果word1[i-1]==word2[j-1]，則table[i][j]==table[i-1][j-1]
2. 如果word1[i-1]!=word2[j-1]，有三種方法可以解決
a replace-> table[i-1][j-1]+1
b insert-> table[i-1][j]+1
c delete-> table[i][j-1]+1
d 找上述三個方法最小值即可
```python!
class Solution(object):
def minDistance(self, word1, word2):
table=[]
for i in range(0,len(word1)+1):
column=[0]*(len(word2)+1)
table.append(column)
for i in range(0,len(word1)+1):
table[i][0]=i
for j in range(0,len(word2)+1):
table[0][j]=j
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
if word1[i-1]==word2[j-1]:
table[i][j]=table[i-1][j-1]
else:
table[i][j]=min(table[i-1][j-1]+1,table[i][j-1]+1,table[i-1][j]+1)
return table[len(word1)][len(word2)]
"""
:type word1: str
:type word2: str
:rtype: int
"""
```
Sign in with Wallet
Connect another wallet