2293 동전1

https://www.acmicpc.net/problem/2293

# top-down
def count(xs, k):
    def rec(i,k, memo):
        key = (i,k)
        if key in memo: return memo[key]
        if k < 0: return 0
        if k == 0: return 1
        ans = 0
        for i in range(i, len(xs)):
            amount = xs[i]
            ans += rec(i, k-amount, memo)
    
        memo[key] = ans
        return ans
    return rec(0,k,{})

top down 으로 제출 시 시간초과로 실패.
시간복잡도?

# bottom-up
def count(xs, k):
    n = len(xs)
    dp = [0]*(k+1)

    for j in range(n):
        for i in range(1, k+1):
            v = xs[j]
            # increment by one
            if i-v == 0:
                dp[i] += 1
            if i-v > 0:
                dp[i] += dp[i-v]
    return dp[k]

bottom up 으로 제출 시 통과.
시간복잡도 O(N*K)
공간복잡도 O(K)

예) xs=[1,2,5], k=7

xs=[1,2,5], k=7, answer=6
----
6가지 케이스
1. 1 1 1 1 1 1 1
2. 1 1 1 1 2
3. 1 1 1 2 2
4. 1 2 2 2
5. 1 1 5
6. 2 5 
----

iteration(1,2,5) 에 따라 dp 배열을 사용하여 이전 값을 사용하여 현재 값을 계산할 지 나열해보자.
dp[i] 는 동전의 합이 i 일 때 주어진 동전들로 만들 수 있는 경우의 수를 의미한다.
최종 문제의 답은 dp[7] 으로 표현될 수 있다. k=7 이 될 수 있는 경우의 수가 dp[7].

   1 2 3 4 5 6 7
[0,0,0,0,0,0,0,0]  intial state
[0,1,1,1,1,1,1,1]  j=0, dp[i] += dp[i-v] where v=xs[0], if i-v == 0: dp[i] += 1
[0,1,2,2,3,3,4,4]  j=1, dp[i] += dp[i-v] where v=xs[1], if i-v == 0: dp[i] += 1
[0,1,2,2,3,4,5,6]  j=2, dp[i] += dp[i-v] where v=xs[2], if i-v == 0: dp[i] += 1

9251 LCS

https://www.acmicpc.net/problem/9251
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1
6
10 20 10 30 20 50
예제 출력 1
4

s1 = input()
s2 = input()

def lcs(s1, s2):
    n1,n2=len(s1),len(s2)
    dp=[[0]*n2 for _ in range(n1)]
    for i in range(n1):
        for j in range(n2):
            if s1[i]==s2[j]:
                dp[i][j] = dp[i-1][j-1]+1 if i>0 and j>0 else 1
            else:
                prev0=dp[i][j-1] if j>0 else 0
                prev1=dp[i-1][j] if i>0 else 0
                dp[i][j]=max(prev0,prev1)
    return dp[-1][-1]
print(lcs(s1, s2))

12852 1로 만들기 2

https://www.acmicpc.net/problem/12852

918. Maximum Sum Circular Subarray

https://leetcode.com/problems/maximum-sum-circular-subarray/