문제를 어떻게 풀어야할지 도저히 모르겠어서 풀이를 블로그랑 질문 글들을 보며 겨우 이해했는데, 그 중 가장 직관적인 풀이가 나와있는 코드를 똑같이 자바로 옮겨서 풀었습니다.  C++ 로 풀다가 자바로 넘어왔는데 DP 관련 문제에서 자주 시간초과가 나오네요...

C++로 제출하면 통과하는데 자바로는 왜 시간초과가 나는 걸까요..? 캐싱하는 부분이 잘안되는거같은데 뭐가 다른지 잘 모르겠습니다.ㅜㅜㅜㅜ 45% 쯤에서 자꾸 터지네요..

보고 공부한 다른 분의 코드는 다음과 같습니다..

#include
using namespace std;
const int INF = 987654321;
int N,temp,up_zero,down_zero;
vector up;
vector down;
int cache[401][401][401];
int solve(int updex, int downdex, int len) {
if (len == 0) {
if (updex == -1 && downdex == -1 && down_zero == 0 && up_zero == 0) return 0;
return -INF;
}
if (updex == -1) {
if (len==up_zero) return 0;
return -INF;
}
if (downdex == -1) {
if (len==down_zero) return 0;
return -INF;
}

int& ret = cache[updex][downdex][len];
if (ret != INF) return ret;
ret = solve(updex - 1, downdex - 1, len - 1) + up[updex] * down[downdex]; //0이 아닌애들끼리 매칭
if (down_zero > 0) { //down 벡터에 0이 있다면
down_zero--;
ret = max(ret, solve(updex - 1, downdex, len - 1)); // up벡터에 0이 아닌애와 매칭
down_zero++;
}

if (up_zero > 0) { // up 벡터에 0이 있다면
up_zero--;
ret = max(ret, solve(updex, downdex - 1, len - 1)); //down 벡터에 0이 아닌애와 매칭
up_zero++;
}
return ret;
}

int main() {
cin >> N;

for (int i = 0;i <= 400;++i)
for (int j = 0;j <= 400;++j)
for (int k = 0;k <= N;++k)
cache[i][j][k] = INF; //memset

for (int i = 0;i < N;++i) {
cin >> temp;
if (temp == 0) up_zero++; // 위 입력에서 0의 갯수
else up.push_back(temp); // 0을 제외한 입력은 up 벡터에 넣기
}
for (int i = 0;i < N;++i) {
cin >> temp;
if (temp == 0) down_zero++; // 아래입력에서 0의 갯수
else down.push_back(temp); // 0을 제외한 입력은 down 벡터에 넣기
}

cout << solve(up.size() - 1, down.size() - 1,N); //up.size()-1 인덱스와 down.size()-1 인덱스까지 고려했을때
// 만들어지는 길이 N;
}