【笔记】二维DP

二维DP的更新可能涉及部分优化：前缀和、滚动数组

核心就是怎么从子问题到原问题

例题

lanqiao1536数字三角形

题目描述

给出一个数字三角形，从顶部到底部可以沿左斜线向下或者右斜线向下，要求数字之和最大，求最大和。

输入描述

• 第一行：包含一个整数N，表示三角形的行数
• 下面N行给出数字三角形，每个数字都是0-99之间的整数。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出描述

输出一个整数，表示最大和

30

解题思路

对于这个题目来说，从上面开始一层层往下加和从下面一层层往上加能得到的最大值应该是一致的。

选取状态1

dp[i][j]表示从第i行第j个往下走的最大和

(1,1)
(2,1)(2,2)
(3,1)(3,2)(3,3)

dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]

• dp[i][j]表示从(i,j)出发到底部的最大和
• a[i][j]表示第i行第j个元素的值
• 最终答案等于第n行dp[n][x]里面最大的一个

代码1

n=int(input())
# 这里用n+1是因为列表下标从1开始
# 用a数组来存储三角形的数值
a=[[0]*(n+1)]
for i in range(n):
    a.append([0]+list(map(int,input().split())))
# 用dp来存储第i行第j个数最大和
dp=[[0]*(n+1) for i in range(n+1)]
# 三角形尖端的值为a的第一行第一个值
dp[1][1]=a[1][1]
for i in range(2,n+1):
    for j in range(1,i+1):
        if j==1:
            dp[i][j]=dp[i-1][j]+a[i][j]
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+a[i][j]
        else:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]

ans=0
for j in range(1,n+1):
    ans=max(ans,dp[n][j])

print(ans)

选取状态2

dp[i][j]表示从第i行第j个往上走的最大和

(1,1)
(2,1)(2,2)
(3,1)(3,2)(3,3)

dp[i][j]=max(dp[i+1][j+1],dp[i+1][j])+a[i][j]

• dp[i][j]表示从(i,j)出发到底部的最大和
• a[i][j]表示第i行第j个元素的值
• 最终答案等于dp[1][1]

代码2

n=int(input())
a=[[0]*(n+1)]
for i in range(n):
    a.append([0]+list(map(int,input().split())))
# 初始化存储最大和的数组
dp=[[0]*(n+1) for i in range(n+1)]
# 从下往上累加
for i in range(n,0,-1):
    for j in range(1,i+1):
    # 边界条件：最后一行的值等于原来的值
        if i==n:
            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[1][1])

lanqiao 389摆花

题目描述

小明在花店门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。规定第i种花不能超过$a_i$盆，摆花时同种花放在一起，且不同种类花需按标号的从小到大排列。

问：一共有多少种不同的摆花方案？

输入描述

第一行包含两个正整数 n和 m，中间用一个空格隔开。

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

2 4
3 2

解题思路

• 状态：dp[i][j]表示前i种花，数量为j盆的方案数，答案为dp[n][m]
• 状态转移：dp[i][j]=dp[i-1][j]+…+dp[i-1][j-a[i]]表示从前i-1种花到第i种花，摆0盆、1盆…、a[i]盆的情况。
• 边界：dp[…][0]=1表示前几种花都没摆的情况

输出描述

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $10^6+7$ 取模的结果。

2

代码

a=[0]+list(map(int,input().split()))
# 状态dp[i][j]前i种花、总数是j盆的方案数，答案是dp[n][m]
dp=[[0]*(m+1) for _ in range(n+1)]
# 状态转移方程：第i种花可以摆0-a[i]盆，所以从第i-1到第i的状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+……+dp[i-1][j-a[i]]
# 边界条件：前面几种花一盆都不放的方案数是1，dp[i][0]=1
# 注意：这里的初始化从0开始，为了给后面的赋值
for i in range(n+1):
  dp[i][0]=1
for i in range(1,n+1):
  for j in range(1,m+1):
    for k in range(min(a[i],j)+1):
      dp[i][j]+=dp[i-1][j-k]
      dp[i][j]%1000007
print(dp[n][m])

lanqiao3711选数异或

题目描述

给定n个正整数a[i]，询问其中有多少个不同的子序列进行异或运算的值为x？

由于结果很大，需要对998244353取模

异或运算：位运算的一种，相同为0，不同为1，参考这个

输入描述

第一行：两个正整数n，x(x<64)

第二行：输入n个正整数

输出描述

输出方案数，对998244353取模

解题思路

原问题：给定n个正整数，求有多少个子序列进行异或运算的值为x，方案数

子问题：前i个正整数，有多少个子序列异或值为j，的方案数

状态：dp[i][j]表示前i个数，子序列异或为j的方案数

状态转移方程：对于第i个数，有选和不选两种可能

• 选
  • xxx^a[i]=j⇒xxx^a[i]^a[i]=j^a[i]⇒xxx=j^a[i]
  • dp[i][j]=dp[i-1][j^a[i]]
• 不选
  • dp[i][j]=dp[i-1][j]

n,x=map(int,input().split())
a=[0]+list(map(int,input().split()))
dp=[[0]*64 for i in range(n+1)]
#只有一个数时，无论选还是不选，都各只有一种可能
dp[1][0]=1
dp[1][a[1]]=1
for i in range(2,n+1):
    for j in range(64):
        dp[i][j]=(dp[i-1][j]+dp[i-1][j^a[i]])%998244353
print(dp[n][x])

lanqiao3348可构造的序列总数

- 题目描述
    - 给定两个数字k和n，需要构造序列满足：
        - 序列长度为n
        - 序列中每个元素区间[1,k]
        - 序列中的下一个元素是上一个元素的倍数
        - 答案很有可能很大，需要对1e9+7取模
- 输入格式
    - 输入一行k，n
- 输出格式
    - 输出一个整数表示答案，答案需要对1e9+7取模
- 解题思路
    - dp[i][j]表示以j结尾的长度为i的序列
    - 状态转移方程就是找i-1长度的j的因数
    - 找j的因数时对其开根号，优化时间复杂度

k, n = map(int, input().split())
mod = int(1e9) + 7
N = 2000

# dp -> 以j数字结尾，长度为i的倍数序列
dp = [[0] * (N + 10) for i in range(N + 10)]
dp[1] = [0] + [1] * (N + 9)
for i in range(1, N + 10): dp[i][1] = 1

# 找num的因数
def check(num):
    ans = []
    for i in range(1, int(num**0.5) + 1):
        if num % i→0:
            ans.append(i)
            ans.append(num // i)
    return set(ans) # 用set去重

# 递推dp数组
for i in range(2, n + 1):
    for j in range(2, k + 1):
        for q in check(j): # q为j的因数
            dp[i][j] += dp[i - 1][q]

ans = 0
for i in range(1, k + 1):
    ans += dp[n][i]
    
print(ans % mod)