[leetcode刷题笔记]动态规划之多维dp问题

记录几道使用动态规划问题。

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

根据三角形的规律，dp[i][j]来源于dp[i-1][j-1]或者dp[i-1][j]，因此状态转移方程为

$dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]$

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[0]*n for _ in range(n)]

        dp[0][0] = triangle[0][0]

        for i in range(1,n):
            dp[i][0] = dp[i-1][0] + triangle[i][0]
       
        for i in range(1,n):
            for j in range(1,i+1):
                if i == j:
                    dp[i][i] = dp[i-1][i - 1] + triangle[i][i]
                else:
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]
    
        return min(dp[-1])

最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

class Solution:
    def maximalSquare(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        m,n= len(matrix),len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        res = 0
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    dp [i][j] = int(matrix[i][j])
                elif int(matrix[i][j]) == 0:
                    dp[i][j] = 0
                else:
                    dp [i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1
                res = max(dp[i][j],res)
        return res*res

统计全为 1 的正方形子矩阵

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的正方形子矩阵的个数。

示例 1：

输入：matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n= len(matrix),len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        res = 0
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    dp [i][j] = matrix[i][j]
                elif matrix[i][j] == 0:
                    dp[i][j] = 0
                else:
                    dp [i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1
                res += dp[i][j]
        return res

注意
1.dp = [[0] * n for _ in range(m)]与dp = [[0] * n ]m的区别
[[0]n]m这种方式是直接将[0]n复制了m遍，是=号复制，若[0]*n发生了更改，则m个都发生更改
2.深拷贝与浅拷贝
浅拷贝是拷贝对象的指针，当原有对象修改时，拷贝对象也会修改。
深拷贝是指源对象与拷贝对象互相独立，其中任何一个对象的改动都不会对另外一个对象造成影响。

最后编辑于：2020.07.16 14:47:19