코인 변경 메모

Question

특정 합계를 변경하는 모든 가능한 방법을 찾기 위해 다음 알고리즘이 실제로 메모를 사용합니까?

func count(n, m) 
    for i from 0 to n 
    for j from 0 to m 
     if i equals 0 
     table[i,j] = 1   
     else if j equals 0 
     table [i,j] = 0 
     else if S_j greater than i 
     table[ i, j ] = table[ i, j - 1 ] 
     else 
     table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ] 
return table[ n, m ] 

함수 카운트가 호출 될 때마다 처음부터 테이블을 채우기 시작합니다. 테이블이 특정 값에 대해 이미 초기화 되었더라도 다음 번 계산이 호출되면이 값을 사용하지 않고 i = 0 및 j = 0에서 다시 시작합니다.

Answer 1

이것은 메모가 아닙니다. 이것은 동적 프로그래밍 코드의 예입니다.

코드를 분석하려면 우선 메모 및 동적 프로그래밍을 구분해야합니다.

Memoization은 Top Down 방식이며 동적 프로그래밍은 Bottom Up 방식입니다.

숫자 n의 계승을 찾는 문제를 고려하십시오.

귀하가 n! 다음 팩트를 사용하여

n! = n * (n-1)! and 0!=1 

이것은 아래로 가기 접근의 예입니다.

n 값은 0! 값이 될 때까지 메모리에 유지됩니다. ~ (n-1)! 반환됩니다. 단점은 많은 스택 메모리를 낭비한다는 것입니다. 이점은 이미 해결 된 하위 문제를 다시 계산할 필요가 없다는 것입니다. 하위 문제에 대한 해결책은 메모리에 저장됩니다.

하지만 문제는 위에서 아래로 접근하지 않아서 메모가 필요하지 않습니다.

테이블의 모든 항목은 이전에 계산 된 하위 문제 솔루션에서 직접 가져옵니다. 거기에 그것은 상향식 접근 방식을 사용합니다. 따라서 동적 프로그래밍을 사용하는 코드 조각이 있습니다.