Algoschool

Explore

Level 1

DP problems

⁠

https://leetcode.com/problems/climbing-stairs/⁠

⁠

Решение:

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]

⁠

https://leetcode.com/problems/unique-paths/⁠

⁠

Решение:

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/unique-paths-ii/⁠

⁠

Решение:

⁠

https://leetcode.com/problems/minimum-path-sum/⁠

⁠

https://leetcode.com/problems/house-robber/

https://leetcode.com/problems/longest-palindromic-substring/

https://leetcode.com/problems/decode-ways/

⁠

https://leetcode.com/problems/coin-change/⁠

⁠

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

⁠

https://leetcode.com/problems/edit-distance/⁠

⁠

"""

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

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]

⁠

https://leetcode.com/problems/coin-change-2/⁠

⁠

"""

1 2

[1,1,1,1,1,1]

[1,1,2,3]

[0,1,2,3,4,5]

"""

class Solution:

def change(self, amount: int, coins: List[int]) -> int:

dp = [0 for i in range(amount + 1)]

dp[0] = 1

for c in coins:

for n in range(1, amount + 1):

if c <= n:

dp[n] += dp[n - c]

print(dp)

return dp[-1]

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.