DP 알고리즘 이론 및 문제

https://velog.io/@bonjaski0989/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-%EC%A0%95%EB%A6%AC%EA%B8%80Python

백준 1463

import sys

n = int(sys.stdin.readline().strip())
dp = [0] * (n+1)
for i in range(2, n+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
print(dp[n])

백준 11726
https://kosaf04pyh.tistory.com/222
https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%8011726%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-2xn-%ED%83%80%EC%9D%BC%EB%A7%81-DP
https://assb.tistory.com/entry/%EB%B0%B1%EC%A4%80-11726%EB%B2%88-2xn-%ED%83%80%EC%9D%BC%EB%A7%81

import sys

    n = int(sys.stdin.readline().strip())
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n] % 10007)

백준 11727

import sys


def main():
    n = int(sys.stdin.readline().strip())
    dp = [0] * (n+2)
    dp[1] = 1
    dp[2] = 3
    # dp[3] = 5
    # dp[4] = 9
    # dp[5] = 21
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]*2

    """
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3
    dp[4] = 5
    |
    || = ㅁ
    ||| =| |= ㅁ| |ㅁ
    |||| =|| |=| ||= == ㅁ|| |ㅁ| ||ㅁ ㅁㅁ =ㅁ ㅁ=
    ||||| ==| =ㅁ| ㅁ=| ㅁㅁ| ||=| |=|| =||| ||ㅁ| |ㅁ|| ㅁ||| |||ㅁ =|= =|ㅁ ㅁ|= ㅁ|ㅁ |== |=ㅁ |ㅁ= |ㅁㅁ |||= 

    |||| + |||= + |||ㅁ
    ||| = || + |= + |ㅁ
    |||||| = ||||| + ||||= + ||||ㅁ
    """
    print(dp[n]%10007)
if __name__ == "__main__":
    main()
"""
n=int(input())
dp=[0,1,3]
for i in range(3,n+1):
    dp.append(dp[i-1]+(dp[i-2]*2))
print(dp[n]%10007)
"""

백준 9095

import sys

import sys


def main():
    number = int(sys.stdin.readline().strip())
    for j in range(1, number + 1):
        n = int(sys.stdin.readline().strip())
        dp = [0] * 12
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4
        for i in range(4, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        print(dp[n])


if __name__ == "__main__":
    main()
"""
number = int(sys.stdin.readline().strip())
for j in range(1, number+1):
    n = int(sys.stdin.readline().strip())
    dp = [0] * (n + 2)
    dp[1] = 1
    dp[2] = 2
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    print(dp[n])
"""
"""
dp[1] = 1 1개
dp[2] = 1+1, 2 2개
dp[3] = 1+1+1, 1+2, 2+1, 3 4개 1 2 1
dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 7개 1 4 2
dp[5] = 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+3+1, 1+1+2+1, 1+2+1+1, 1+2+2, 13개
        2+1+1+1, 2+1+2, 2+2+1, 2+3,
        3+1+1, 3+2
1+1 +1
1+ 2
3

1+1+1 +1 4
1+1+ 2 2
1+ 3 1
"""

# 1+1+1+1+1
# 1+1+1+1 +1 : 7개
# 1+1+1 +2 : 4개
# 1+1+ 3 : 2개

백준 10844번
0으로 시작하는 수는 계단수가 아니다. 라고 되어있는데 왜 dp[i][j]에서 j가 0일때도 경우의수에 포함시키는 건지 이해가안된다.
https://infinitt.tistory.com/106
https://cotak.tistory.com/12
https://pacific-ocean.tistory.com/151

import sys


def main():
    n = int(sys.stdin.readline().strip())
    dp = [[0] * 10 for _ in range(n+1)]
    for i in range(1, 10):
        dp[1][i] = 1
    mod = 1000000000
    for i in range(2, n+1):
        for j in range(10):
            if j == 0:
                dp[i][j] = dp[i-1][1]
            elif j == 9:
                dp[i][j] = dp[i-1][8]
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
    print(sum(dp[n]) % mod)
    for i in dp:
        for j in i:
            print(j, end= ' ')
        print()
if __name__ == "__main__":
    main()