https://programmers.co.kr/learn/courses/30/lessons/42895

1.完全なコード

def solution(N, number):
    answer = -1
    if N == number:
        return 1
    d = [set() for i in range(9)]
    for i in range(1, 9):
        d[i].add(int(str(N) * i))  # [5, 55, 555, 5555...]
    for i in range(2, 9):
        for j in range(1, i):
            # 예) 5자리 숫자를 만들기 위해서는
            # 1+4, 2+3, 3+2, 4+1 네 개의 경우가 존재한다.
            # [j] 와 [i-j] 의 합은 항상 5가 나온다.
            for op1 in d[j]:
                for op2 in d[i-j]:
                    d[i].add(op1 + op2)
                    d[i].add(op1 - op2)
                    d[i].add(op1 * op2)
                    if op2 != 0:
                        d[i].add(op1 // op2)
        if number in d[i]:
            answer = i
            break
    return answer


solution(5, 12)

2.後期

この間,DP問題を解く際にnumberに対応するdpテーブルを作成し,1から値を充填し,既存値を用いてd[number]を求める.しかし、この問題はそんなことはできません.
N使用回数(1~8)に適合するDPテーブルを全て記憶することは考えにくい.思いもよらなかった.この問題はdpの原因であり[j]と[i−j]が既存値を利用する部分から確認できる.