기억화 검색과 dp의 기본 사상을 간단히 분석하다.

몇몇 블로그를 보고 기억 검색과 dp 간의 관계를 총결해 냈다
01 가방과 같은 유형의 모든 아이템에 대해 선택하거나 선택하지 않는 두 가지 상태의 문제에 대해 우리는 먼저 폭수에서 착안하여 이 문제를 생각한다
예컨대 로곡p1048

int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
    if( tleft < 0 ) return;
    if( pos == n+1 ){
        ans = max(ans,tans);
        return;
    }
    dfs(pos+1,tleft,tans);
    dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    dfs(1,t,0);
    cout << ans << endl;
    return 0;
}

어떤 '외부 변수' (dfs 함수 외에 값이 dfs가 실행됨에 따라 바뀌는 변수) 를 빌리지 않고 답을 기록하려고 합니다.
답안을 반환값으로 기록하다

int n,time;
int tcost[103],mget[103];
int dfs(int pos,int tleft){
    if(pos == n+1)
        return 0;
    int dfs1,dfs2 = -INF;
    dfs1 = dfs(pos+1,tleft);
    if( tleft >= tcost[pos] )
        dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
    return max(dfs1,dfs2);
}
int main(){
    cin >> time >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    cout << dfs(1,time) << endl;
    return 0;
}

같은pos와tleft에 대해 dfs의 반환값은 항상 같습니다!
생각해 봐도 이상하지 않습니다. 왜냐하면 우리의 dfs는 어떠한 외부 변수에도 의존하지 않기 때문입니다.
tcost[103], mget[103] 같은 물건은 외부 변수라고 할 수 없다. 왜냐하면 그녀들은 dfs 과정에서 변하지 않기 때문이다.
그리고?
모든 dfs (pos,tleft의 반환 값을 기록할 수 있는 그룹을 만듭니다. 처음에mem의 모든 값을 -1-3-1로 설정합니다. (방문하지 않은 것을 의미합니다.)매번 dfs에 들어가기 전에 (우리의 dfs는 귀속 호출됩니까)mem[pos][tleft]가 -1-3-1인지 확인하고, 정상적으로 실행하고 답안을 mem에 기록합니까? 그렇지 않으면?
mem의 값을 직접 되돌려줍니다!
 

int n,t;
int tcost[103],mget[103];
int mem[103][1003];
int dfs(int pos,int tleft){
    if( mem[pos][tleft] != -1 ) return mem[pos][tleft];
    if(pos == n+1)
        return mem[pos][tleft] = 0;
    int dfs1,dfs2 = -INF;
    dfs1 = dfs(pos+1,tleft);
    if( tleft >= tcost[pos] )
        dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
    return mem[pos][tleft] = max(dfs1,dfs2);
}
int main(){
    memset(mem,-1,sizeof(mem));
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    cout << dfs(1,t) << endl;
    return 0;
}

이때mem의 의미는 dfs와 같습니다.
타임 tleft에서 채집 후pos개 약초로 얻을 수 있는 최대 수익
 
기억화 검색이 무엇인지 정리해 보자.

외부 변수에 의존하지 않음

답안은 반환값의 형식으로 존재하지만 매개 변수의 형식으로 존재할 수 없다(즉 dfs를 dfs(pos,tleft,nowans)로 정의할 수 없으며 이 안의 nowans는 요구에 부합되지 않는다).

같은 그룹의 매개 변수에 대해 dfs 반환값은 항상 같다

기억화 검색과 동적 기획의 관계: 기억화 검색은 dp이다
 
타임 tleft에서 채집 후pos개 약초로 얻을 수 있는 최대 수익
이게 dp 상태 아니에요?
위 코드에서 확인할 수 있는 내용은 다음과 같습니다.
dfs(pos,left)=max(dfs(pos+1,tleft−tcost[pos])+mget[pos] , dfs(pos+1,tleft)
즉
mem[pos][tleft]=max(mem[pos+1][tleft−tcost[pos]]+mget[pos] , mem[pos+1][tleft])
이것은 dp의 상태 이동이 아닙니까?
요약:
기억화 검색과 동적 기획은 근본적으로 말하면 하나의 물건으로 어떠한 dp방정식도 기억화 검색으로 바뀔 수 있다. 반대로도 마찬가지다.
구현

기억화 검색의 매개 변수에 따라 dp의 상태를 직접 얻을 수 있고 반대로

기억화 검색의 귀속 관계에 따라 상태 이동 방정식을 쓸 수 있다. 이 방정식은 순환식 dp를 직접 쓸 수 있다. 단지 반대일 뿐이다. (왜?)반대로

대부분의 기억화 검색 시공 복잡도는 최적화되지 않은 dp와 완전히 같다

가장 중요한 점: 양자 사상이 유사하다!!핵심 사상은 모두 같은 매개 변수에 대한 답안이 같은 특성을 이용하여 같은 매개 변수(순환식의 dp는 수조 하표로 나타난다)에 대해 그 답안을 기록하고 중복 계산을 없애고 시간 복잡도를 최적화하는 역할을 한다.이것이 바로 양자의 정수입니다.**

위의 내용은 블로그를 참조하십시오.https://interestinglsy.blog.luogu.org/memdfs-and-dp

원리 분석

큰 놈의 블로그를 보고 나서 dp의 사상에 대해 새롭고 깊이 있는 인식을 가지게 되었다. 그리고 나는 왜 같은 문제와 방정식 dp가 순환하는 방식으로 기억화 검색의 매번 두 가지 상태로 돌아가는 모델을 실현할 수 있는지 생각했다.
먼저 귀속의 실현 방식을 이야기하면 두 갈래 나무의 도형으로 요약할 수 있다
모든 물품은 두 개의 노드를 선택하거나 선택하지 않을 수 있다.pos와tleft는 검색에 있어pos~n의 모든 사용 상황을 달려갈 수 있기 때문에 기억화 검색은 이미 검색한pos와tleft를 먼저 기록할 수 있다.같은pos와tleft를 만났을 때 계속 아래로 검색하지 않고 직접 값을 얻을 수 있다.
같은 사상을 통해 dp의 실현과 연결되고 상태가 이동하는 과정에서 기억화 검색은 이미 선택한 상태(즉 현재 물품을 선택하거나 선택하지 않은 상태)를 다음 층의 귀속에 전달하는 것이다. 이렇게 하면 이 나무의 최하층 노드에서 상층을 통해 전달하는 상태이다. 나는 이 마지막 물품을 선택하거나 선택하지 않기로 결정하고 비교적 큰 (최우선 상황)의 값을 이전 층의 귀속에 되돌린다.같은 방식으로 최상층으로 전달된 상태에서 첫 번째 아이템을 선택했는지, 마지막에 최대치를 얻는다.
밤을 들다
지금 가방의 용량이 C=10이라고 가정해 봅시다.
아이템 번호: 1 2 3
아이템 무게: 5 6 4
아이템 가치: 20 10 12
검색의 사상으로 보면 첫 번째 전달은 바로 제가 첫 번째 물품인pos+1, C-5와pos+1을 선택한 것입니다. C는 이런 식으로 아래로 전달하는 상태입니다. 연상하는 dp도 상태를 옮겨야 합니다. 그러나 제 dp는 두 층의 순환을 통해 이루어진 것이기 때문에 매번 전달하는 것이 저에게 필요한 상태입니다. 어떻게 해야 합니까?윗글에서 제시한 바와 같이 dp과정은 반대로 이루어진다. 첫 번째 물품을 귀속의 최하층으로 간주하고 내가 위로 전달하는 상태라고 생각했다. 이 전달 상태는 내가 상부에서 나에게 어떤 수요가 있는지 잘 모르겠다. 나는 나의 현재 수요와 상부가 서로 다른 선택으로 인해 발생할 수 있는 상태를 모두 고려한 후에표를 열거하여 이 표를 전체적으로 상층(다음 물품의 선택)에 전달하고 말하기가 까다롭다. 밤의 dp 데이터를 열거하여 분석한다.
dp:0 0 0 0 0 0 0 0 0 0

i=1:
dp[10] = max(dp[5]+20, dp[10]);
dp[9] = max(dp[4]+20, dp[9]);
dp[8] = max(dp[3]+20, dp[8]);
dp[7] = max(dp[2]+20, dp[7]);
dp[6] = max(dp[1]+20, dp[6]);
dp[5] = max(dp[0]+20, dp[5]);

dp: 0 0 0 0 20 20 20 20 20 20

이 줄의 dp수조를 분석하면 왜 dp수조에 4개의 0이 있는지 알 수 있다. 0과 20의 상황을 분리해서 보면 검색에서 선택한 것과 선택하지 않은 두 가지 상황을 연상할 수 있다. 그 4개의 0은 바로 dp[1]가 현재 물품을 선택하지 않은 상황에서 9개의 공간을 남기고 dp[2]가 선택하지 않은 상황에서 8개의 공간을 남기는 것이다.왜 선택하지 않은 상황에서 모든 상황을 열거합니까?이것은 바로 dp상태 이동과 검색의 차이점이다. 검색은 위에서 아래로 전달되는 상태이기 때문에 나는 서로 다른 조합을 통해 내가 한 번의 선택에서 내가 선택한 몇 가지 상태가 발생하는지 알 수 있다. dp는 아래에서 위로 전달되는 상태이기 때문에 나는 모든 상태를 열거해서 앞으로 내가 위로 전달할지 말지 선택할 수 있는 상태 중 하나를 열거할 수 밖에 없다. 계속해서 몇 개의 데이터를 열거해서 보자.

i=2:
dp[10] = max(dp[6]+4, dp[10]);
dp[9] = max(dp[3]+10, dp[9]);
dp[8] = max(dp[2]+10, dp[8]);
dp[7] = max(dp[1]+10, dp[7]);
dp[6] = max(dp[0]+10, dp[6]);
dp: 0 0 0 0 20 20 20 20 20 20 //    ， 10      20    

다시 두 번째 그룹의 데이터를 보면 여기도 두 가지 상황을 선택해야 한다. 물품의 질이 6이기 때문에 6부터 선택할 수 있다. 그 앞에 있는 dp[1]-dp[5]는 모두 1과 2를 선택하지 않는 상황이다. 1과 2를 동시에 선택할 수 없기 때문에 dp[6]-dp[10]는 1과 2에서 가장 큰 상황이다. 현재의 2호로 모든 상태를 다시 한 번 갱신한 셈이다.
 

i=3:
dp[10] = max(dp[6]+12, dp[10]);
dp[9] = max(dp[5]+12, dp[9]);
dp[8] = max(dp[4]+12, dp[8]);
dp[7] = max(dp[3]+12, dp[7]);
dp[6] = max(dp[2]+12, dp[6]);
dp[5] = max(dp[1]+12, dp[5]);
dp[4] = max(dp[0]+12, dp[4]);

dp: 0 0 0 12 20 20 20 20 32 32

같은 이치로 dp[3]도 세 번째 물품의 데이터로 전체 수조를 한 번 갱신하고 놓거나 놓지 않는 것에 따라 앞의 상태에서 상태를 선택하여 이동(이미 최우선)하고 놓거나 놓지 않는 것이 결과에 미치는 영향을 비교하여 결과를 얻는다.
dp[10]는 가방 용량이 10일 때 가장 큰 가치로 요구하는 값입니다.