동적 프로그래밍 - 프리미티브 계산기

Question

동적 프로그래밍을 사용하여 다음 문제를 해결하려고합니다.

현재 숫자 x로 다음 세 가지 연산을 수행 할 수있는 기본 계산기가 제공됩니다. x를 2로 곱하고 x에 3을 곱하거나 x에 1을 더합니다. 당신의 목표에는 양의 정수 n이 주어지며, 숫자 1부터 시작하여 숫자 n을 얻는 데 필요한 최소 연산 수를 찾으십시오. 출력에는 최소 연산 수와 1에서 n으로 얻는 시퀀스의 두 부분이 포함되어야합니다

이 게시물에서 다음 해결책을 찾았습니다 : Dynamic Programming - Primitive Calculator Python.

나는 사람이 뒤에 논리를 설명 할 수 없습니다 "[] K = N = 번호"문제 에서 시작 부분을 추적 등을 이해하는 데?

def dp_min_ops(n): 
    all_parents = [None] * (n + 1) 
    all_min_ops = [0] + [None] * n 

    for k in range(1, n + 1): 
     curr_parent = k - 1 
     curr_min_ops = all_min_ops[curr_parent] + 1 

     if k % 3 == 0: 
      parent = k // 3 
      num_ops = all_min_ops[parent] + 1 
      if num_ops < curr_min_ops: 
       curr_parent, curr_min_ops = parent, num_ops 

     if k % 2 == 0: 
      parent = k // 2 
      num_ops = all_min_ops[parent] + 1 
      if num_ops < curr_min_ops: 
       curr_parent, curr_min_ops = parent, num_ops 

     all_parents[k], all_min_ops[k] = curr_parent, curr_min_ops 

    numbers = [] 
    k = n 
    while k > 0: 
     numbers.append(k) 
     k = all_parents[k] 
    numbers.reverse() 

    return all_min_ops, numbers 

print(dp_min_ops(5)) # ([0, 1, 2, 2, 3, 4], [1, 3, 4, 5]) 
print(dp_min_ops(10)) # ([0, 1, 2, 2, 3, 4, 3, 4, 4, 3, 4], [1, 3, 9, 10]) 

Answer 1

힌트 : 숫자 N에 도달하기 위해 최소 작업을 찾으려면 그것은 다음과 같이

코드는 ... 마법처럼 작동합니다. (n은 2로 나눌 경우 경우))

  min_operations[n/2] 

3

1) min_operations[n-1]

2) (n)은 3으로

  min_operations[n/3] 

나누어 다음과 같은 답변을해야합니다

이제 위의 세 가지 작업 중 최소 작업을 발견하면이 세 가지 중 최소 하나에 하나를 추가하여 n에 도달하는 최소 작업 수가 생깁니다 (유효 할 경우).

이제는 1에 도달하는 최소 작업 수가 0이라는 것을 알고 있습니다. 이제 최소 연산 수를 1에서 n으로 계산하기 시작합니다. 당신이 어떤 숫자를 계산할 때마다 k라고 말하면 k보다 적은 모든 숫자에 대해 항상 답을 얻을 것입니다. k-1, k/2 (나눌 수있는 경우), k/3 (나눌 수있는 경우). 따라서 1에서 n까지의 모든 숫자에 대한 답을 찾는다면 n을 계산할 수 있습니다.