[数据结构]递归、回溯、分治、动态规划

发表于
参加Datawhale的编程计划的第7个任务，涉及递归、回溯、分治、动态规划，用python实现。。

练习

Regular Expression Matching（正则表达式匹配）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        dp=[[False for i in range(len(p)+1)] for j in range(len(s)+1)]
        dp[0][0]=True
        for i in range(1,len(p)+1):
            if p[i-1]=='*':
                if i>=2:
                    dp[0][i]=dp[0][i-2]
        for i in range(1,len(s)+1):
            for j in range(1,len(p)+1):
                if p[j-1]=='.':
                    dp[i][j]=dp[i-1][j-1]
                elif p[j-1]=='*':
                    dp[i][j]=dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                else:
                    dp[i][j]=dp[i-1][j-1] and s[i-1]==p[j-1]
        return dp[len(s)][len(p)]

Minimum Path Sum（最小路径和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]: return 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    before = 0
                elif i == 0:
                    before = grid[i][j-1]
                elif j == 0:
                    before = grid[i-1][j]
                else:
                    before = min(grid[i-1][j], grid[i][j-1])
                grid[i][j] = before + grid[i][j]
        return grid[m-1][n-1]

Coin Change （零钱兑换）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        n = len(coins)
        # dp[i]表示amount=i需要的最少coin数
        dp = [float("inf")] * (amount+1)
        dp[0] = 0
        for i in range(amount+1):
            for j in range(n):
                # 只有当硬币面额不大于要求面额数时，才能取该硬币
                if coins[j] <= i:
                    dp[i] = min(dp[i], dp[i-coins[j]]+1)
        # 硬币数不会超过要求总面额数，如果超过，说明没有方案可凑到目标值
        return dp[amount] if dp[amount] <= amount else -1

递归

回溯

分治

动态规划

相关链接

编程计划的第7个任务
第七次任务 打卡表格