Learn dynamic programming in Python (A ~ E)

Learn dynamic programming through the Educational DP Contest / DP Summary Contest (A ~ E)

A - Frog 1 There are N scaffolds. The scaffolds are numbered 1,2,…, N. For each i (1 ≤ i ≤ N) the height of the scaffold i is hi. Initially, there is a frog on scaffold 1. The frog repeats the following actions several times, trying to reach scaffolding N. Scaffolding i when in scaffolding i+1 or i+Jump to 2. At this time, if the scaffolding of the jump destination is j, the cost|hi−hj|Pay. Find the minimum total cost that the frog will pay to reach scaffold N.

Frog1.py


N = 6
h = [30 10 60 10 60 50]

def frog1(N, h):
  dp = [float('inf')]*(N)
  dp[0]=0
  dp[1]=abs(h[0]-h[1])
  if N>=2:
    for i in range(2,N):
      dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
  print(dp[-1])
  
frog1(N,h)

The cost is 0 for scaffold 1. The cost is abs (h0-h1) because scaffold 2 can only be routed from scaffold 1. Therefore, there are multiple options for scaffolding 2 and above, but for scaffolding i, the only options are scaffolding i-1 or i-2. min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2])) Is calculated as the cost of scaffolding i.

B - Frog 2 There are N scaffolds. The scaffolds are numbered 1,2,…, N. For each i (1 ≤ i ≤ N), the height of the scaffold i is hi. Initially, there is a frog on scaffold 1. The frog repeats the following actions several times, trying to reach scaffolding N. When in scaffold i, jump to one of scaffold i + 1, i + 2,…, i + K. At this time, if the scaffolding of the jump destination is j, the cost|hi−hj|Pay. Find the minimum total cost that the frog will pay to reach scaffold N.

Frog2.py


N,K = 10,4
h = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
 
def frog2(N,k,h):
  dp = [float("inf")]*N
  dp[0]=0
  for i in range(1,N):
    for j in range(1,K+1):
      if i-j >= 0:
        dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
      else: 
        break
  print(dp[-1])
  
frog2(N,K,h)

A pattern with more choices for jumping problems. It can be solved just by making a nested structure of for. Finally, [0, 30, 20, 30, 40, 30, 20, 30, 40, 40] Will be.

C - Vacation Taro's summer vacation will start tomorrow. Taro decided to make a plan for the summer vacation. Summer vacation consists of N days. For each i (1 ≤ i ≤ N), on day i, Taro chooses one of the following activities. A: Swim in the sea. Get happiness ai. B: Get rid of insects in the mountains. Get happiness bi. C: Do your homework at home. Get happiness ci. Taro is tired of it, so he can't do the same activity for more than two days in a row. Find the maximum value of the total happiness that Taro gets.

vacaton.py


N = 3
c = [[10,40,70],[20,50,80],[30,60,90]]

def vacation(N,c):
  dp = [[0]*(3) for _ in range(N+1)]
  for i in range(N):
    for j in range(3):
      for k in range(3):
        if i==0 or j!=k:
          dp[i+1][j] = max(dp[i+1][j], dp[i][k]+c[i][j])
      
  print(max(dp[-1]))
  
vacation(N,c)

Calculate when A is selected, when B is selected, and when C is selected in each procedure, and the final maximum procedure is calculated backward. [[0, 0, 0], [10, 40, 70], [90, 120, 120], [150, 180, 210]] Will be.

D - Knapsack 1 There are N items. Items are numbered 1,2,…, N. For each i (1 ≤ i ≤ N), the item i weighs wi and has a value of vi. Taro chose some of the N items and decided to put them in a knapsack and take them home. The capacity of the knapsack must be W, and the total weight of the items to be brought back must be W or less. Find the maximum sum of the values ​​of the items that Taro brings back.

knapsack1.py


N,W = 3,8
c = [[3, 30],[4,50],[5,60]]

def knapsack1(N,W,c):
  dp = [[0]*(W+1) for _ in range(N+1)]
  for i in range(N):
    for j in range(W+1):
      if c[i][0] <= j:
        dp[i+1][j] = max(dp[i][j],dp[i][j-c[i][0]]+c[i][1])
      else:
        dp[i+1][j] = dp[i][j]
  
  print(dp[-1][-1])
  
knapsack1(N,W,c)

A typical problem of the knapsack problem. The number is piled up with for i in range (N), and the weight is expressed with for j in range (W + 1). Both the value and the weight can be considered by adding the value obtained by subtracting the weight of the overlapping items from j.

E - Knapsack 2 There are N items. Items are numbered 1,2,…, N. For each i (1 ≤ i ≤ N), the item i weighs wi and has a value of vi. Taro chose some of the N items and decided to put them in a knapsack and take them home. The capacity of the knapsack must be W, and the total weight of the items to be brought back must be W or less. Find the maximum sum of the values ​​of the items that Taro brings back.

knapsack2.py


N,W = 3,8
c = [[3, 30],[4,50],[5,60]]

def knapsack1(N,W,c):
  dp = [[0]*(W+1) for _ in range(N+1)]
  for i in range(N):
    for j in range(W+1):
      if c[i][0] <= j:
        dp[i+1][j] = max(dp[i][j],dp[i][j-c[i][0]]+c[i][1])
      else:
        dp[i+1][j] = dp[i][j]
  
  print(dp[-1][-1])
  
knapsack1(N,W,c)

Recommended Posts

Learn dynamic programming in Python (A ~ E)
[Python] Dynamic programming TDPC A
Try a functional programming pipe in Python
Python programming in Excel
[Python] Dynamic programming ABC015D
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
AtCoder ABC 177 Python (A ~ E)
Take a screenshot in Python
Create a function in Python
Create a dictionary in Python
AtCoder ABC 178 Python (A ~ E)
[Python] Dynamic programming knapsack problem
[Python] Dynamic programming TDPC D
Solve ABC176 E in Python
Learn cumulative sum in Python
AtCoder ABC 176 Python (A ~ E)
Paiza Python Primer 1 Learn Programming
Make a bookmarklet in Python
Solve Atcoder ABC176 (A, B, C, E) in Python
Draw a heart in Python
A Python program in "A book that gently teaches difficult programming"
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Maybe in a python (original title: Maybe in Python)
Write a binary search in Python
GUI programming in Python using Appjar
Functional programming in Python Project Euler 1
[python] Manage functions in a list
Hit a command in Python (Windows)
Functional programming in Python Project Euler 3
Draw a scatterplot matrix in python
ABC166 in Python A ~ C problem
Write A * (A-star) algorithm in Python
Create a binary file in Python
Solve ABC036 A ~ C in Python
Start SQLite in a programming language
Write a vim plugin in Python
Write a depth-first search in Python
Template AtCoder ABC 179 Python (A ~ E)
Implementing a simple algorithm in Python 2
Functional programming in Python Project Euler 2
Solve ABC037 A ~ C in Python
Run a simple algorithm in Python
Draw a CNN diagram in Python
Create a random string in Python
Schedule a Zoom meeting in Python
When writing a program in Python
Programming with Python / JavaScript / VBScript inline scripting in Automation Anywhere A 2019
Generate a first class collection in Python
Learn the design pattern "Builder" in Python
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Solve ABC175 A, B, C in Python
Use print in a Python2 lambda expression
A simple HTTP client implemented in Python
Do a non-recursive Euler Tour in Python
Learn the design pattern "Flyweight" in Python
I made a payroll program in Python!
Precautions when pickling a function in python
Learn the design pattern "Observer" in Python
Learn the design pattern "Memento" in Python
Learn the design pattern "Proxy" in Python
Write the test in a python docstring