메모와 동적 프로그래밍의 차이점은 무엇입니까?

메모와 동적 프로그래밍의 차이점은 무엇입니까?

---

메모와 동적 프로그래밍의 차이점은 무엇입니까? 동적 프로그래밍은 메모리의 하위 집합이라고 생각합니다. 맞아?

---

메모와 동적 프로그래밍의 차이점은 무엇입니까?

메모 화 는 이전에 계산 된 결과를 캐시하고 동일한 계산이 다시 필요할 때 캐시 된 결과를 반환하는 최적화 기술을 설명하는 용어입니다.

동적 프로그래밍 은 재귀 적 특성의 문제를 반복적으로 해결하는 기술이며 하위 문제의 계산이 겹칠 때 적용 할 수 있습니다.

동적 프로그래밍은 일반적으로 테이블을 사용하여 구현되지만 메모를 사용하여 구현할 수도 있습니다. 보시다시피 어느 쪽도 다른 쪽의 "서브셋"이 아닙니다.

---

합리적인 후속 질문은 다음과 같습니다. 표 (일반적인 동적 프로그래밍 기술)와 메모의 차이점은 무엇입니까?

도표를 사용하여 동적 프로그래밍 문제를 해결할 때 문제를 " 상향식 "으로 해결합니다. 즉, 일반적으로 n 차원 테이블 을 채워서 관련된 모든 하위 문제를 먼저 해결 합니다. 표의 결과를 기반으로 "상위"/ 원래 문제에 대한 솔루션이 계산됩니다.

메모를 사용하여 문제점을 해결하는 경우 이미 해결 된 하위 문제점의 맵을 유지 보수하여 문제점을 해결하십시오. "top"문제를 먼저 해결한다는 의미에서 " top down "을 수행합니다 (일반적으로 하위 문제를 해결하기 위해 반복).

여기 에서 좋은 슬라이드 (링크는 이제 죽었습니다, 슬라이드는 여전히 좋습니다) :

• 모든 하위 문제를 한 번 이상 해결해야하는 경우 상향식 동적 프로그래밍 알고리즘은 일반적으로 상수 요인으로 하향식 메모리 알고리즘보다 성능이 뛰어납니다.
  • 재귀를위한 오버 헤드가없고 테이블을 유지하기위한 오버 헤드가 적습니다.
  • 동적 프로그래밍 알고리즘에서 규칙적인 테이블 액세스 패턴을 이용하여 시간 또는 공간 요구 사항을 더욱 줄일 수있는 몇 가지 문제점이 있습니다.
• 하위 문제 공간의 일부 하위 문제를 전혀 해결할 필요가없는 경우, 메모 화 된 솔루션은 반드시 필요한 하위 문제 만 해결하는 이점이 있습니다

추가 자료 :

• 위키 백과 : 메모 , 동적 프로그래밍
• 관련 SO Q / A : 동적 프로그래밍을위한 메모 화 또는 테이블 방식

---

이것은 기사로 다시 작성되었습니다 여기에 .

---

동적 프로그래밍은 주어진 복잡한 문제를 하위 문제로 나눔으로써 주어진 문제를 해결하고 동일한 결과를 다시 계산하지 않도록 하위 문제의 결과를 저장하는 알고리즘 패러다임입니다.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Memoization은 이전에 해결 된 솔루션 (종종 배열을 기반으로하는 테이블과 달리 해시 키 값 쌍으로 구현 됨)을 쉽게 추적하여 다시 발생할 때 다시 계산되지 않도록하는 쉬운 방법입니다. 상향식 또는 하향식 방법 모두에서 사용할 수 있습니다.

메모와 표에 대한이 토론 을 참조하십시오 .

따라서 동적 프로그래밍은 반복 관계 / 재귀를 해결하고 이전에 찾은 솔루션을 표 또는 메모를 통해 저장함으로써 특정 클래스의 문제를 해결하는 방법입니다. Memoization은 이전에 해결 된 문제에 대한 솔루션을 추적하는 방법이며 특정 입력 세트에 대해 고유 한 결정적 솔루션이있는 모든 기능과 함께 사용할 수 있습니다.

---

다이나믹 프로그래밍은 종종 Memoization이라고합니다!

1. Memoization은 하향식 기술 (주어진 문제를 분해하여 시작)이고 동적 프로그래밍은 상향식 기술 (사소한 하위 문제에서 주어진 문제에 이르기까지 시작)

2. DP는 기본 사례에서 시작하여 솔루션을 찾고 그 위로 진행합니다. DP는 모든 하위 문제를 해결합니다.

   필요한 하위 문제 만 해결하는 Memoization과 달리

3. DP는 지수 시간 무차별 대입 솔루션을 다항식 시간 알고리즘으로 변환 할 가능성이 있습니다.

4. DP는 반복적이므로 훨씬 더 효율적일 수 있습니다.

   반대로, 메모 화는 재귀로 인한 오버 헤드에 대한 비용을 지불해야합니다.

더 간단하게, Memoization은 하향식 접근 방식을 사용하여 문제를 해결합니다. 즉 핵심 (주요) 문제로 시작한 다음 하위 문제로 나누고 이와 유사한 하위 문제를 해결합니다. 이 방법에서는 동일한 하위 문제가 여러 번 발생하고 더 많은 CPU주기를 소비 할 수 있으므로 시간 복잡성이 증가합니다. 동적 프로그래밍에서 동일한 하위 문제는 여러 번 해결되지 않지만 이전 결과는 솔루션을 최적화하는 데 사용됩니다.

---

(1) 개념적으로 , 메모 화와 DP 는 실제로 같은 것입니다. DP의 정의 : "중복 하위 문제"및 "최적 하위 구조"를 고려하십시오. 메모 화에는 이러한 2가 있습니다.

(2) Memoization은 DP이며 스택 오버플로의 위험은 재귀가 깊습니다. DP 상향식에는 이러한 위험이 없습니다.

(3) 메모 화에는 해시 테이블이 필요합니다. 추가 공간과 조회 시간.

따라서 질문에 대답하십시오.

- 개념적 으로 (1)은 동일한 것을 의미합니다.

(2)를 고려할 때, 정말로 원한다면 메모는 DP의 하위 집합입니다. 어떻게하면 메모로 해결할 수있는 문제는 DP로 해결할 수 있지만 DP로 해결할 수있는 문제는 메모로 해결할 수 없습니다 (왜냐하면) 오버플로가 발생할 수 있음).

-(3)을 고려하면 성능에 약간의 차이가 있습니다.

---

위키 백과에서 :

메모 화

컴퓨팅에서 memoization은 이전에 처리 된 입력에 대한 결과 계산을 반복하지 않고 함수 호출을 통해 컴퓨터 프로그램 속도를 높이는 데 주로 사용되는 최적화 기술입니다.

다이나믹 프로그래밍

수학 및 컴퓨터 과학에서 동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제로 분류하여 해결하는 방법입니다.

문제를 더 작은 / 간단한 하위 문제로 나눌 때 종종 동일한 하위 문제가 한 번 이상 발생하므로 메모를 사용하여 이전 계산 결과를 저장하므로 반복 할 필요가 없습니다.

동적 프로그래밍은 종종 메모를 사용하는 것이 적합한 상황에 처하게되지만 다른 기법을 사용하지 않고도 두 기법 중 하나를 사용할 수 있습니다.

---

Memoization과 Dynamic Programming은 개별 하위 문제를 한 번만 해결합니다.

Memoization은 재귀를 사용하고 하향식으로 작동하지만 동적 프로그래밍은 반대 방향으로 이동하여 문제를 상향식으로 해결합니다.

아래는 흥미로운 비유입니다.

하향식 -먼저 내가 세상을 장악한다고 말합니다. 어떻게 하시겠습니까? 당신은 내가 먼저 아시아를 인수 할 것이라고 말합니다. 어떻게 하시겠습니까? 먼저 인도를 인수하겠습니다. 나는 델리 등의 장관이 될 것입니다.

상향식 -당신은 내가 델리의 CM이 될 것이라고 말합니다. 그런 다음 인도를 인수하고 아시아의 다른 모든 국가를 인수하고 마지막으로 세계를 인수합니다.

---

나는 예를 들어 가고 싶다 .

문제:

계단을 오르고 있습니다. 상단에 도달하려면 n 단계가 필요합니다.

매번 1 ~ 2 단계 올라갈 수 있습니다. 정상까지 몇 가지 뚜렷한 방법으로 올라갈 수 있습니까?

메모와 함께 재귀

이런 식으로 메모 배열을 사용하여 재귀 트리를 잘라 내고 (나무 또는 관목에서 과잉 재료 제거) 재귀 트리의 크기를 nn까지 줄입니다.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

다이나믹 프로그래밍

이 문제는 하위 문제로 나눌 수 있으며 최적의 하위 구조 속성을 포함합니다. 즉, 하위 문제의 최적 솔루션에서 최적의 솔루션을 효율적으로 구성 할 수 있으므로 동적 프로그래밍을 사용하여이 문제를 해결할 수 있습니다.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

예는 https://leetcode.com/problems/climbing-stairs/ 에서 가져옵니다.

참고 URL : https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming