동적 기획

안녕하세요.
이 블로그에서, 우리는 당신에게 동적 프로그래밍의 진정한 의미와 그것을 어떻게 사용하는지 제공하려고 합니다.
명확한 이해를 제공하기 위해 우리는 매우 흔히 볼 수 있는 문제인 Fibonacci급수를 참고할 것이다. 우리는 이것에 대해 매우 잘 알고 있다.
이 문제를 해결하는 데는 여러 가지 방법이 있다.그들은 다음과 같습니다.

귀속

DP 상단/하단

DP

공간 최적화 방법.

우리는 모든 방법을 상세하게 토론할 것이다.
그럼 시작합시다!
1. 귀속
우리는 귀속에서 함수가 특정한 문제를 해결하기 위해 기본 상황에 도달할 때까지 여러 번 자신을 호출한다는 것을 안다.만약 우리가 처음에 귀속이 도대체 어떻게 일을 하는지 이해하려고 시도했다면, 이것은 문제가 될 것이다. 우리는 곤혹스러울 수도 있고, 문제를 해결할 방법을 찾지 못할 수도 있다.우선, 우리는 큰 문제와 그것을 어떻게 해결하는지에 관심을 가져야 한다.그리고 우리는 함수를 정의하고 멈추는 위치를 알려야 한다. 즉, 기본 상황을 지정하고 코드를 작성해서 더 큰 문제를 해결하고, 나머지는 귀속 처리에 맡겨야 한다.
피보나치 급수처럼 우리는 첫 번째 항목이 1이고 n번째 항목이 앞의 두 항목의 총계, 즉 n-1과 n-2라는 것을 안다.우리들은 그것을 쓰고 나머지는 귀속에 남겨 두자.

int fibonacci(int n)
{
    if(n==1 || n==0)
        return n;
    return fibonacci(n-1)+fibonacci(n-2);
}

위의 함수는 매우 잘 작동할 것이다. 그러나 이것이 가장 좋은 방법입니까?
그것을 이해해 봅시다.상술한 함수를 사용한다고 가정하면, 우리는 다섯 번째 피보나 항목을 찾으려고 시도한다.위의 코드는 다음 귀속 트리를 생성합니다.

일부 원소에 대해 트리가 여러 번 반복되는 것을 볼 수 있다. 즉, 같은 작업이 한 번 또 한 번 진행된다는 것이다.큰 숫자에 대해서는 중복되는 횟수가 더 높다.그 밖에 위의 코드의 시간 복잡도는 O(2^n)로 지수급이어서 매우 나쁘다.
그래서 상기 문제의 답은 정해지지 않았다. 이것은 가장 좋은 방법이 아니다.
걱정할 거 없어요.😊. 동태적인 계획은 이 문제를 해결할 것이다.
그렇다면 동적 기획은 무엇일까?
윈스턴 처칠의 한마디:
역사에서 교훈을 얻지 못한 사람들은 반드시 전철을 밟을 것이다.
이것이 바로 동적 기획이 한 일이다.우리는 재계산을 피하기 위해 필요할 때 사용할 수 있도록 계산된 값을 저장합니다.
우리 토론 좀 합시다!
2. DP의 톱다운
우리가 큰 하위 문제에서 시작하여 기본적인 상황에 도달했을 때, 우리는 위에서 아래로의 DP 방법이라고 부른다.이런 방법에서 우리는 귀속+기억, 즉 귀속계산값을 사용하여 특정한 수조에 저장한다. 그러면 우리는 다시 계산할 필요가 없다.
이런 방법으로 피보나치 급수 문제를 어떻게 해결하는지 봅시다.

int dp[100]={0}; // I am assuming size to be 100. It can be anything
int fibonacci(int n)
{
    if(n==0||n==1)
        return n;
    if(dp[n]!=0)
        return dp[n]; //If the value has already been calculated, return it
    dp[n] = fibonacci(n-1)+fibonacci(n-2);
    return dp[n];
}

위의 코드는 어때요?돌아가는 것보다 훨씬 낫다.
따라서 상기 코드의 시간 복잡도는 O(N)이고 공간 복잡도도 필수적이다.
3. 하향식 DP
이런 방법에서 우리는 기본적인 상황으로부터 출발하여 필요한 해결 방안을 얻어낸다.이런 방법은 귀속될 필요가 없다.
코드 좀 봐.

int fibonacci(int n)
{
    int dp[100]={0}; // I am assuming size to be 100. It can be anything
    dp[1]=1; //We need to provide starting values
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

시간과 공간의 복잡성은 상술한 것과 같다, 즉 O(N).
나는 위의 설명과 코드가 당신이 동적 프로그래밍이 무엇인지, 그리고 그것이 어떻게 작동하는지에 대해 약간의 생각과 체험을 할 수 있기를 바랍니다.걱정 마.나는 네 번째 부분을 잊지 않았다.이것은 DP와 관계가 크지 않기 때문에, 나는 아래에서 토론할 것이다😊.
따라서 위의 토론에서 우리는 DP가 코드를 고도로 최적화하고 메모리 등 계산 자원을 절약했다는 결론을 얻을 수 있다.
동적 계획에 능통하려면 많은 실천이 필요하고 다른 알고리즘을 이해하는 것도 최상의 DP 솔루션을 얻는 데 도움이 될 수 있다.
지금은 공간 최적화 방법의 때다.
4. 공간 최적화 방법
이런 방법은 반드시 모든 문제에 적용되는 것은 아니다. 왜냐하면 그것은 피보나치 서열에 적용되기 때문이다.이런 방법에서 어떤 수조를 사용하지 않아도 우리는 n번째 원소를 찾을 수 있다!
봐봐.

int fibonacci(int n)
{
    int a=0,b=1,c;
    for(int i=2;i<=n;i++)
    {
        c=a+b;
        a=b;
        b=c;
    }
    return c;
}

그럼 우리 여기서 블로그를 끝냅시다.
모든 독자들에게 감사하는 시간.어떠한 피드백도 환영합니다.여러분도 제가 곧 발표할 블로그에서 보실 수 있기를 바랍니다.
감사합니다.😊.