Целое число переполнений в динамическом программировании - почему ответ все еще правильный? [закрыто] ⇐ JAVA

[Anonymous]

Я внедрил три версии проблемы с минимальной затратой (рекурсивный, сверху вниз DP и снизу вверх DP). Я подозреваю, что в моей реализации нисходящего вниз могут быть ошибки, особенно вокруг целочисленного переполнения и проверки меморизации, но она дает правильные ответы даже при экстремальных тестовых случаях. реализация < /h3>
public static int topDown(int[][] maze){
int M = maze.length;
int N = maze[0].length;
int[][] dp = new int[M][N];
return helper(maze,0,0,dp);
}

public static int helper(int[][] maze,int i,int j,int[][] dp){
topDown++;
int M = maze.length;
int N = maze[0].length;

if(i > M - 1 ) return Integer.MAX_VALUE-maze[i-1][j];
if(j > N - 1) return Integer.MAX_VALUE-maze[j-1];

if(i == M - 1 && j == N - 1) return maze[j];

if(dp[j] != 0) return dp[j];

dp[j] = Math.min(
maze[j] + helper(maze,i+1,j,dp),
maze[j] + helper(maze,i,j+1,dp)
);

return dp[j];
}
< /code>
тестовый пример с большими значениями < /h3>
int[][] maze = {
{1, -5},
{2, 3}
};
< /code>
Ожидаемое поведение: расчет (integer.max_value -(-5) ... должно вызвать переполнение целочисленного. /> Существуют ли тестовые случаи, когда эта реализация не удалась? /> Протестировано со значениями вблизи integer.max_value: кажется, работает < /li>
Прослеживается через рекурсию вручную < /li>
< /ul>

Подробнее здесь: https://stackoverflow.com/questions/797 ... ll-correct