当前位置：首页 > article >正文

【算法】动态规划专题③ ——二维DP python

article 2025/2/6 10:44:53

前置知识

【算法】动态规划专题① ——线性DP python

进入正题

三角形最小路径和 https://leetcode.cn/problems/triangle/

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：

在这里插入图片描述

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

思路：

dp[ $i$ ][ $j$ ]表示从triangle[ $i$ ][ $j$ ]往下走的最小路径和
写出状态转移方程： dp[ $i$ ][ $j$ ] = min(dp[ $i$ + 1][ $j$ ], dp[ $i$ + 1][ $j$ + 1]) + triangle[ $i$ ][ $j$ ]即可

题解code：

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

趁热打铁

数字三角形 https://www.lanqiao.cn/problems/1536/learning/?page=1&first_category_id=1&problem_id=1536

一样的题目，仅仅是最小路径和换成了最大路径和，快来AC吧

附上题解：

n = int(input())
a = [[0] * n for _ in range(n)]
for row in range(n):
    a[row] = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
    for j in range(i + 1):
        if i == n - 1:
            dp[i][j] = a[i][j]
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]
print(dp[0][0])

实战演练

摆花 https://www.lanqiao.cn/problems/389/learning/?page=1&first_category_id=1&problem_id=389

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的种花，从1到n标号。
为了在门口展出更多种花，规定第i种花不能超过a[i]盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。

输入描述
第一行包含两个正整数n和m,中间用一个空格隔开。
第二行有n个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、…an.
其中，0<n≤100,0<m≤100,0≤ai≤100。

输出描述
输出只有一行，一个整数，表示有多少种方案。
注意：方案数可能很多，请输出方案数对1e6+7取模的结果。

输入输出样例：

输入

2 4
3 2

输出

思路：

翻译下题目：
给定n种花，第 $i$ 种花数量不超过ai,需要凑出m盆，求方案数。
定义：dp[ $i$ ][ $j$ ]表示 $i$ 种花，不超过 $j$ 盆的方案数
答案即为dp[ $n$ ][ $m$ ]
总的能选m盆，第i种花选了x盆，则前i-1种花就只能选m-x盆
得出：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ··· + dp[i-1][j-a[i]]

题解code：

mod = 10 ** 6 + 7
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    dp[i][0] = 1
    for j in range(1, m + 1):
        # 前i种花摆j盆 = 第i种花摆的盆数 + 前i-1种花摆的盆数
        # dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ··· + dp[i-1][j-a[i]]
        for k in range(min(a[i], j) + 1):
            dp[i][j] += dp[i - 1][j - k]
            dp[i][j] %= mod
print(dp[n][m])

小试牛刀

选数异或 https://www.lanqiao.cn/problems/3711/learning/?page=1&first_category_id=1&problem_id=3711

问题描述

给定几个正整数a[i]，询问你其中有多少个不同子序列进行异或（⊕）运算的值为x?
由于结果很大，你需要对998244353取模。
异或运算：位运算的一种，符号为⊕，1⊕1=0,1⊕0=1,0⊕0=0.
子序列：从初始序列中选出若干个数保持原有顺序的序列。

输入格式
第一行输入两个正整数n，x
第二行输入n个正整数

输出格式
输出选择不同子序列进行异或（⊕)运算的值为x的方案数，对998244353取模。

样例输入

2 0
2 2

样例输出

说明
方案有同时选择两个 2 和一个数都不选。

评测数据规模
1≤n≤1e5,0≤a[i]≤63,0≤x≤63

思路：

定义dp[ $i$ ][ $j$ ]: 前 $i$ 个数异或和为 $j$ 的方案数
dp[ $i$ ][ $j$ ] = 前 $i$ -1个数的方案数 + 第 $i$ 个数的方案
对于第 $i$ 个数，我们考虑选或不选
不选第 $i$ 个数：dp[ $i$ -1][ $j$ ] , 选：dp[ $i$ -1][ $j$ ^ a[ $i$ ]]
得到状态转移方程： dp[ $i$ ][ $j$ ] = dp[ $i$ - 1][ $j$ ] + dp[ $i$ - 1][ $j$ ^ a[ $i$ ]]
ans即为dp[ $n$ ][ $x$ ]

异或运算性质可以点此进入详细讲解

题解code：

mod = 998244353
n, x = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [[0] * 64 for _ in range(n + 1)]  # x<=63
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(64):
        # dp[i][j]:前i个数异或和为j的方案数
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ a[i]]
        # 不选第i个数：dp[i-1][j],选：dp[i-1][j^a[i]]
        dp[i][j] %= mod

print(dp[n][x])