Skip to content
DP problems
Решение:
class Solution(object):
def climbStairs(self, n):
if n == 1:
return 1
dp = {1:1, 2:2}
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Решение:
class Solution(object):
def uniquePaths(self, m, n):
dp = [[0 for i in range(n)] for j in range(m)]
for i in range(n):
dp[0][i] = 1
for j in range(m):
dp[j][0] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
Решение:
https://leetcode.com/problems/house-robber/
https://leetcode.com/problems/longest-palindromic-substring/
https://leetcode.com/problems/decode-ways/
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
maxVal = amount + 1
dp = [maxVal for i in range(amount + 1)]
dp[0] = 0
for sum_ in range(amount + 1):
for coin in coins:
if amount >= coin:
dp[sum_] = min(dp[sum_], 1 + dp[sum_ - coin])
return dp[-1] if dp[-1] != maxVal else -1
"""
dp[i, j] = мин ко-во действий
do[1, 1]
dp[i, j] = | a == b => dp[i, j] = dp[i - 1][j - 1]
| a != b. => 1 + dp[i - 1][j]
1 + dp[i][j - 1]
1 + dp[i - 1][j - 1]
'' hob
'' aro
dp[3][2] = hor => ro
''
h
ho
hor
hors
horse
ros => ''
0 1 2 3 4 5
'' h o r s e
0 '' 0 1 2 3 4 5
1 r 1 1 2 2 3 4
2 o 2 2 1 2 3 4
3 s 3 4 2 2 2 3
"""
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0 for i in range(len(word2) + 1)]
for j in range(len(word1) + 1)]
for i in range(len(dp)):
dp[i][0] = i
for j in range(len(dp[0])):
dp[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]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(1 + dp[i][j - 1], 1 + dp[i - 1][j], 1 + dp[i - 1][j - 1])
return dp[-1][-1]
"""
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ··· in the right corner or using a keyboard shortcut (
CtrlP
) instead.