Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "053 --055 Dynamic Programming: Others".

2. Summary

As you can see from "Other", these three questions are a little different from the previous `` `dp``` in terms of orientation (preference?) I felt that.

3. Main story

053 --055 Dynamic programming: Other

053. DPL_1_D --Longest increasing subsequence

Answer

import bisect

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [A[0]]

for i in range(1, n):
    if A[i] > dp[-1]:
        dp.append(A[i])
    else:
        ind = bisect.bisect_left(dp, A[i])
        dp[ind] = A[i]

print(len(dp))

It is solved by binary search and DP.

dpIn ascending orderaWe will add the elements of. In particular,

1. For all A elements ```A [i] `` `
2. Add anything larger than the last element of `dp``` to `dp```
3. If it is not large, there are numbers greater than or equal to A [i] `` `in` `` dp, so replace it with ```A [i] `` `
4. The answer is the length of the completed dp is.

054. AtCoder Beginner Contest 006 D --Trump Insertion Sort

Answer

import bisect

N = int(input())
C = [int(input()) for _ in range(N)]

dp = [C[0]] #initial value

for i in range(1, N):
    if C[i] > dp[-1]:
        dp.append(C[i])
    else:
        ind = bisect.bisect_left(dp, C[i])
        dp[ind] = C[i]

print(N - len(dp))

53. DPL_1_D --Longest increasing subsequence is almost the same. The difference is the last ``` print (N --len (dp))` ``. The number of times you need to insert playing cards is the number of playing cards minus the length of the longest increasing subsequence.

55. AtCoder Beginner Contest 134 E - Sequence Decomposing

Answer

import bisect
from collections import deque

N = int(input())
A = [int(input()) for _ in range(N)]

dp = deque()
dp.append(A[0])

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    else:
        dp[ind-1] = A[i]

print(len(dp))

Let's change the way of thinking from the above two problems. In the above two problems, the elements above the maximum value of `` `dpwereappend, This time, the elements below the minimum value are appendleft```.