코인 변경 분석

Question

{1,3,5} 명칭 동전; 합계 = 11 특히 동적 프로그래밍을 사용 합이 나는이 동전 변화 문제의 실행 시간 복잡도를 검색

(우리는 각 교단의 동전의 번호를 사용할 수 있습니다) 확인하는 데 사용할 수있는 동전의 최소 수를 찾을 수 방법. 그러나 어디에서나 설명을 찾을 수 없었습니다.

비 동적 솔루션의 복잡성을 계산 한 다음 동적 솔루션의 복잡성을 어떻게 계산합니까? (안 욕심 일)

편집 : 여기

는 분석 질문을 받았다되는 구현입니다.

public int findCoinChange(int[] coins, int sum,int count) { 

    int ret = 0, maxRet = -1; 
    if(sum ==0)maxRet = count; 
    else if(sum < 0)maxRet = -1; 
    else{ 
     for(int i:coins){ 
      ret = findCoinChange(coins, sum - i,count+1); 
      if(maxRet< 0)maxRet = ret; 
      else if(ret >=0 && ret < maxRet){ 
        maxRet = ret; 
       } 
      } 
    } 
    if(maxRet < 0)return -1; 
    else return maxRet; 
} 

나에게도 조합 폭발이 발생합니다. 그러나 나는 이것을 위해 런타임 복잡성을 어떻게 추론 할 지 확신하지 못한다.

Answer 1

이 문제에 대한 dynamic programming solution이 이다 명확하게O(k * n) (중첩 루프, ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ) k 동전의 수이고 n는 그 변화가 이루어지고 금액이다.

비 동적 프로그래밍 솔루션의 의미를 모르겠습니다. 죄송합니다. 어떤 알고리즘을 사용할지 지정해야합니다. 어떤 경우에는 greedy algorithm fails이므로 은이 아닙니다. 선형 프로그래밍 솔루션을 의미합니까? 복잡성이 무엇인지 알지 못하기 때문에이 문제에 대한 끔찍한 접근 방식이며, 임의로 천천히 실행하는 것이 가능합니다.

또한 "동적 인 것으로 변경하십시오."라는 것이 무엇인지 알지 못합니다.