This article is for DP beginners. If you are interested in DP in the first place, please read Kenchon's article!
Recently I started studying DP ** Techniques to reduce the dimension of DP ** I was very impressed with it, so I will write an article! !! !!
I would like to briefly explain the following two questions while actually solving them.
-TDPC A-Contest ** → DP from 2D to 1D ** -ABC 015 D --Takahashi-kun's suffering ** → DP from 3D to 2D **
This is a typical subsum problem. The problem this time is that MAX of N is 100 → Bit full search is impossible in terms of computational complexity, so consider it in DP.
Normally, when you solve DP as two dimensions, it looks like this
DP_2D.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
#############################
N = I()
p = LI()
dp = [[0]*10001 for _ in range(N+1)] #0:That score does not exist, 1:That score exists
dp[0][0] = 1
for i,j in itertools.product(range(1,N+1),range(10001)):
pi = p[i-1]
if j-pi>=0:
dp[i][j] = max(dp[i][j],dp[i-1][j-pi]) #If you choose
dp[i][j] = max(dp[i][j],dp[i-1][j]) #If you do not choose
print(sum(dp[-1])) #Output the number of numbers 1
To make this DP1 dimension, do this!
DP_1D.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
#############################
N = I()
p = LI()
dp = [0]*10001 #0:That score does not exist, 1:That score exists
dp[0] = 1
for i,j in itertools.product(range(1,N+1),range(10001)[::-1]):
pi = p[i-1]
if j-pi>=0:
dp[j] = max(dp[j],dp[j-pi]) #If you choose
#dp[j] = max(dp[j],dp[j]) #If not selected → Not required
print(sum(dp)) #Output the number of numbers 1
** The point is here! !! !! ** **
range(10001)[::-1]
Range (10000, -1, -1)
is also acceptable** You can reuse dp by turning the loop from the opposite side! !! !! !! !! This is the technique! !! !! !! !! ** **
If you use dp and turn the loop in order For example, when p = 2 points,
dp = [1,0,1,0,1,0,1,0,1 ・ ・ ・]
And 4 points, 6 points, 8 points ... will also exist ...
Because
dp[j] = max(dp[j],dp[j-pi])
Since 2 points are 1, 4 points are also 1. .. ..
Since 4 points are 1, 6 points are also 1. .. ..
・ ・ ・
** But if you loop from the opposite ... **
dp = [1,0,1,0,0,0,0,0,0 ・ ・ ・]
dp[j] = max(dp[j],dp[j-pi])
・ ・ ・ Since 4 points are 0, 6 points will also be 0! Since 2 points are 0, 4 points will also be 0! Since 0 points are 1, 2 points become 1! !! !! ** So you can get the correct result while using dp around! !! !! !! !! !! !! !! !! → You can reduce the dimension of dp from 2D to 1D! !! !! !! !! !! !! !! !! !! ** **
** By lowering the dimension of dp, I'm so happy that the amount of thinking in my head has decreased! ** **
I wonder if this impression can be transmitted ~ ** Please tell me ~ **
Another question to make you feel more impressed! !! !!
Difficulty: 1388 light blue problem! A slightly more advanced problem with one more variable in the knapsack DP.
If you think about DP in 3D, it's not impossible, but my head seems to be punk ...
DP_3D.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
#############################
W = I()
N,K = LI()
AB = [LI() for _ in range(N)]
dp = [[[0]*(W+1) for _ in range(K+1)] for _ in range(N)] #Holds the maximum value of importance when using k sheets
for i,k,w in itertools.product(range(N),range(1,K+1),range(W+1)):
A,B = AB[i]
if w-A>=0:
dp[i][k][w] = max(dp[i][k][w],dp[i-1][k-1][w-A]+B)
dp[i][k][w] = max(dp[i][k][w],dp[i-1][k][w])
print(dp[-1][-1][-1])
However, with this, ** Python is computationally TLE, and PyPy is MLE **. Owata ...
**here! Using the dimensionality reduction technique I mentioned earlier, Can't you manage to use DP? ** ** When I think about it ... ** Apparently it can be made 2D ...! ** **
DP_2D.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
#############################
W = I()
N,K = LI()
AB = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(K+1)] #Holds the maximum value of importance when using k sheets
for i,k,w in itertools.product(range(N),range(1,K+1)[::-1],range(W+1)[::-1]):
A,B = AB[i]
if w-A>=0:
dp[k][w] = max(dp[k][w],dp[k-1][w-A]+B)
#dp[k][w] = max(dp[k][w],dp[k][w])
print(dp[-1][-1])
** The point is here! !! !! ** **
range(1,K+1)[::-1],range(W+1)[::-1]
From the opposite, loop around and use DP! !! !!
** The result you are interested in is ... **
** As usual, Python was TLE, but w (dimension reduction did not reduce the amount of calculation w) It became AC safely with PyPy ~! !! !! ** **
If the dimension is likely to be more than 2 dimensions when the DP problem comes out in the future, Let's think about whether this dimension reduction technique can be used ~
**end! !! !! ** **
Recommended Posts