前置知识
进入正题
三角形最小路径和 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 i i][ j j j]表示从triangle[ i i i][ j j j]往下走的最小路径和
写出状态转移方程： dp[ i i i][ j j j] = min(dp[ i i i + 1][ j j j], dp[ i i i + 1][ j j j + 1]) + triangle[ i i i][ j j 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]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
趁热打铁
数字三角形 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])
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
实战演练
摆花 https://www.lanqiao.cn/problems/389/learning/?page=1&first_category_id=1&problem_id=389
题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的种花，从1到n标号。
为了在门口展出更多种花，规定第i种花不能超过a[i]盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入描述 输出描述 输入输出样例： 输入 输出 思路： 翻译下题目： 题解code： 选数异或 https://www.lanqiao.cn/problems/3711/learning/?page=1&first_category_id=1&problem_id=3711 问题描述 给定几个正整数a[i]，询问你其中有多少个不同子序列进行异或（⊕）运算的值为x? 输入格式 输出格式 样例输入 样例输出 说明 评测数据规模 思路： 定义dp[
i
i
i][
j
j
j]: 前
i
i
i个数异或和为
j
j
j的方案数 题解code： 二维动态规划是解决涉及两个维度变化问题的一种动态规划方法。它通常用于处理那些可以通过构建一个二维表格来记录中间结果，从而优化求解过程的问题。 END
第一行包含两个正整数n和m,中间用一个空格隔开。
第二行有n个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、…an.
其中，0
输出只有一行，一个整数，表示有多少种方案。
注意：方案数可能很多，请输出方案数对1e6+7取模的结果。2 4
3 2
2
给定n种花，第
i
i
i种花数量不超过ai,需要凑出m盆，求方案数。
定义：dp[
i
i
i][
j
j
j]表示
i
i
i种花，不超过
j
j
j盆的方案数
答案即为dp[
n
n
n][
m
m
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]]
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])
小试牛刀
由于结果很大，你需要对998244353取模。
异或运算：位运算的一种，符号为⊕，1⊕1=0,1⊕0=1,0⊕0=0.
子序列：从初始序列中选出若干个数保持原有顺序的序列。
第一行输入两个正整数n，x
第二行输入n个正整数
输出选择不同子序列进行异或（⊕)运算的值为x的方案数，对998244353取模。2 0
2 2
2
方案有同时选择两个 2 和一个数都不选。
1≤n≤1e5,0≤a[i]≤63,0≤x≤63
dp[
i
i
i][
j
j
j] = 前
i
i
i-1个数的方案数 + 第
i
i
i个数的方案
对于第
i
i
i个数，我们考虑选或不选
不选第
i
i
i个数：dp[
i
i
i-1][
j
j
j] , 选：dp[
i
i
i-1][
j
j
j ^ a[
i
i
i]]
得到状态转移方程： dp[
i
i
i][
j
j
j] = dp[
i
i
i - 1][
j
j
j] + dp[
i
i
i - 1][
j
j
j ^ a[
i
i
i]]
ans即为dp[
n
n
n][
x
x
x]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])
总结
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢
评论记录：
回复评论：