DFS--기억 DFS--DP 간의 연계

제가 DP라는 데서 계속 난리가 났어요. 2017년 교정문제(출력 1, 2, 3...n과 m의 모든 가능한 조합)를 풀 때 DFS를 사용했는데 그 후에 DP와 어떻게 닮았는지 찾았어요. 그리고 사내들이 이 문제를 어떻게 봤는지 찾아봤는데 그 정도 연관이 있었어요.
디지털 삼각형을 예로 들면 하나의 디지털 삼각형을 제시하는데 맨 끝부터 끝까지 많은 경로가 있는데 경로의 최대와 최대를 구한다.
예: 7
3   8
8   1   0
2   7   4   4
4   5   2   6   5
소박한 DFS의 생각은 (0, 0)부터 다음 단계(아래 또는 오른쪽 아래)의 최대치와 현재 점의 값을 구하는 것이다.

 int dfs(int x,int y) //    x ， y               ，dfs（0,0）     。
{
       //    
       if(x > numCount - 1)
              return 0;
       //    (x,y),          ,    ,(0,0)        
       return max(dfs(x+1,y),dfs(x+1,y+1)) + num[x][y];
}

이를 통해 알 수 있듯이 소박한 DFS는 대량의 중복 계산을 한다. 예를 들어 중간의 한 점에 대해 그는 어느 한 점의 아래이자 다른 한 점의 오른쪽 아래이다.
기억 DFS란 위에 있는 DFS의 결과를 저장하는 것으로 사용할 때 직접 사용하고 다시 반복할 필요가 없다.

//result        
int dfs(int x,int y)
{
    if(x > numCount - 1)
       return 0;
    //    ，   
    if(result[x][y] != -1)
       return result[x][y];
return result[x][y] = max(dfs(x+1,y),dfs(x+1,y+1)) + num[x][y];
}

종합적으로 보면 소박한 DFS와 기억화된 DFS는 모두 귀속 사상을 바탕으로 계산한 것이다. 귀속을 이용하는 조건은 두 가지가 있다. 첫째, 해결해야 할 문제를 새로운 문제로 바꿀 수 있고 이 새로운 문제의 해결 방법은 변하지 않지만 문제의 규모는 줄어든다.둘째는 역귀출구가 있어야 한다.
예를 들어 여기서 우리는 dfs(x+1, y)와 dfs(x+1, y+1)를 통해 (x, y)를 구하고 x가 줄보다 많을 때 퇴출한다.
DP Dynamic Planning 은 상태를 배열로 직접 저장하여 상태와 상태 간에 이동합니다.

//numCount         
for(int i = numCount - 1; i >= 0; i--)
       for(int j = 0;j <= i; j++)
             //
             result[i][j] = max(result[i+1][j],result[i+1][j+1]) + num[i][j];

result 수조 공간은 삼각형보다 1이 크고 모두 0으로 초기화되며 Dp의 계산 과정은 삼각형의 마지막 줄인result[numCount-1][j],result[i+1][j]가 실제 의미에서 존재하지 않고 여기는 1과 같기 때문에 이 줄의 계산 결과는 그 자체이고 그 다음에 한 줄을 (0,0)까지 계산하여 문제를 최종적으로 풀 수 있다.
이를 통해 알 수 있듯이 기억화 DFS와 DP 동적 기획은 모두 중간 결과를 저장했다. 서로 다른 것은 두 사람의 생각이 정반대이다. DP는 아래에서 위로 계산하고 기억화 DFS는 위에서 아래로 계산하기 때문이다.