[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]

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 **

TDPC A --Contest

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.

DP: 2D Ver

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

DP: 1D Ver

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]

** 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! !! !!

ABC 015 D --Takahashi-kun's Anguish

Difficulty: 1388 light blue problem! A slightly more advanced problem with one more variable in the knapsack DP.

DP: 3D Ver

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 ... スクリーンショット 2021-01-15 16.25.39.png

DP: 2D Ver

**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 ... **

スクリーンショット 2021-01-15 6.32.02.png ** 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

[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
How to enjoy programming with Minecraft (Ruby, Python)
[Write to map with plotly] Dynamic visualization with plotly [python]
[Python] Sumitomo Mitsui Trust Bank Programming Contest 2019 C (How to use DP) [AtCoder]
Solve AtCoder 167 with python
3. 3. AI programming with Python
Python programming with Atom
Competitive programming with python
[Python] Dynamic programming ABC015D
Programming with Python Flask
Try to solve the programming challenge book with python3
Programming with Python and Tkinter
Connect to BigQuery with Python
Solve AtCoder ABC166 with python
Light blue with AtCoder @Python
I wanted to solve the Panasonic Programming Contest 2020 with Python
Atcoder Acing Programming Contest Python
[Python] Dynamic programming knapsack problem
Knowledge you need to know when programming competitive programming with Python2
Connect to Wikipedia with Python
[Python] Dynamic programming TDPC D
Post to slack with Python 3
Switch python to 2.7 with alternatives
Write to csv with Python
Things to keep in mind when using Python with AtCoder
An introduction to Python Programming
Solve AtCoder ABC 186 with Python
[Python] Dynamic programming TDPC A
Network programming with Python Scapy
How to log in to AtCoder with Python and submit automatically
atcoder Review of Panasonic Programming Contest 2020, up to question E (Python)
IPynb scoring system made with TA of Introduction to Programming (Python)
Tips to know when programming competitively with Python2 (Other language specifications)
Python: How to use async with
Link to get started with python
[Introduction to Python3 Day 1] Programming and Python
[Python] Write to csv file with Python
Create folders from '01' to '12' with python
Nice to meet you with python
Dynamic proxy with python, ruby, PHP
Try to operate Facebook with Python
[Python] Object-oriented programming learned with Pokemon
Output to csv file with Python
Convert list to DataFrame with python
MP3 to WAV conversion with Python
To do tail recursion with Python2
Solve AtCoder Problems Recommendation with python (20200517-0523)
How to get started with Python
Easy Python + OpenCV programming with Canopy
What to do with PYTHON release?
Unable to install Python with pyenv
How to use FTP with Python
Solved AtCoder ABC 114 C-755 with Python3
How to calculate date with python
Easily post to twitter with Python 3
I want to debug with Python
Python --Reduce photos beautifully with antialiasing