동적 프로그래밍(DP) 캐싱의 문제점:
dp[505][505][505] 배열을 사용하여 cm 함수의 결과를 캐싱합니다.
초기값은 모두 0입니다.
if(dp[x][y][z]) return dp[x][y][z];
이 코드는 dp[x][y][z] 값이 0일 경우, 캐싱된 값이 없다고 판단하고 다시 계산합니다.
문제: 만약 cm 함수가 계산 결과로 유효한 값 0을 반환할 수 있다면, 이 조건문은 항상 false가 되어 중복 계산이 발생합니다.
이는 DP의 목적에 어긋나며, 심한 경우 시간 초과를 유발할 수 있습니다.
해결책: 캐싱 여부를 확인할 별도의 visited 배열을 사용하거나, 반환 값에 1을 더해서 저장하는 등(저장 시 +1, 반환 시 -1)의 방법으로 0과 '계산 안 됨' 상태를 구분해야 합니다.
도움이 되면 좋겠네요!

aiden3233 11달 전
틀린부분 지적까진 바라지 않으니 반례 몇개만 찾아주실수 있나요?