[11053/백준/파이썬] 가장 긴 증가하는 부분 수열 - DP

---

소스코드

A = int(input())

numlist = list(map(int,input().split()))

dp = [1]*A

for i in range (A):

  for j in range (i):

    if numlist[i] > numlist[j]:

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

print(max(dp))

---

알고리즘

numlist= [10, 20, 10, 30, 20, 50,]

위의 예시를 바탕으로 만약 6개의 계단이 있다고 생각을 해보자

무조건 숫자가 커야 올라가는 것이다.

- 1번 계단 10 : 1번 밟으면 끝이다.

- 2번 계단 20 : 1번 계단 -> 2번계단 2번 밟는다.

- 3번 계단 10 :

숫자가 커야 올라갈 수 있으므로 20 -> 10은 안된다.

10 -> 10 한번 밟았다고 생각하자.

- 4번 계단 30 :

10 -> 20 ->  30 3번 밟는다.

이런 식으로 생각하면 된다.