http://www.acmicpc.net/problem/1932

dp를 이용해서 푸는 문제, 일단 iterative로 풀면

d[1][1] = A[1][1]; for(int i=2; i<=N; i++) for(int j=1; j<=i; j++) d[i][j] = max( d[i-1][j-1], d[i-1][j]) + A[i][j]; 대충 이렇게 할수 있는데 이걸 recursive로 하면

int cache[505][505]; //(y, x)위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환 int path(int y, int x){ //기저 사례 if(y == N-1) return a[y][x]; //메모이제이션 int& ret = cache[y][x]; if(ret != -1) return ret; return ret = max(path(y+1, x), path(y+1, x+1)) + a[y][x]; } 이렇게 recursive함수를 만들 수 있다 recursive는 처음이라 문화컬쳐

큰 차이는 iterative는 위에서 아래로 내려가지만 

recursive는 아래에서 위로 올라가도록 구성했다는 것이다

어떤게 더 빠른지는 잘 모르겠는데 boj랑 알고스팟에서 실행시간이 달랐다 테스트케이스가 달라서 그런듯

듣자하니 메모이제이션을 사용하다가 호출을 존나게 하다보면 스택 오버플로우가 발생할수도 있다고 한다

또 듣자하니 잘하는사람은 dp를 할떄 recursive로 한단다 난 벌레니까 iterative로 해야지

근데 고수될려면 recursive로도 해봐야겠다

참고로 모든 iterative로 만든 프로그램은 recursive형태로 바꿀수 있고 그 반대도 가능하다고 한다

'알고리즘' 카테고리의 다른 글

꿈틀꿈틀  (0) 2013.07.30
에라토스테네스의 체  (0) 2013.07.30
LCS(longest common subsequence)  (0) 2013.07.16
바이너리서치 할때 주의할점  (0) 2013.07.14
dfs, bfs  (0) 2013.07.14
Posted by bogus919
,