動的計画法における「事後性なし」を理解する

第174問：ダンジョンゲーム公式解答

Javaコード：

import java.util.Arrays;
public class Solution {
 public int calculateMinimumHP(int[][] dungeon) {
 int rows = dungeon.length;
 int cols = dungeon[0].length;
 // 1ビットを追加する理由を理解する
 int[][] dp = new int[rows + 1][cols + 1];
 for (int i = 0; i <= rows; i++) {
 Arrays.fill(dp[i], Integer.MAX_VALUE);
 }
 // dpを初期化する[rows - 1][cols - 1] = 1
 dp[rows][cols - 1] = 1;
 dp[rows - 1][cols] = 1;
 for (int i = rows - 1; i >= 0; i--) {
 for (int j = cols - 1; j >= 0; j--) {
 int minVal = Math.min(dp[i + 1][j], dp[i][j + 1]);
 dp[i][j] = Math.max(minVal - dungeon[i][j], 1);
 }
 }
 return dp[0][0];
 }
}

Pythonのコード：

from typing import List
class Solution:
 def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
 rows = len(dungeon)
 cols = len(dungeon[0])
 dp = [[9999 for _ in range(cols + 1)] for _ in range(rows + 1)]
 dp[rows][cols - 1] = 1
 dp[rows - 1][cols] = 1
 for i in range(rows - 1, -1, -1):
 for j in range(cols - 1, -1, -1):
 min_val = min(dp[i + 1][j], dp[i][j + 1])
 dp[i][j] = max(min_val - dungeon[i][j], 1)
 return dp[0][0]

C++コード：

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
 int calculateMinimumHP(vector<vector<int>> &dungeon) {
 int rows = dungeon.size();
 int cols = dungeon[0].size();
 vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, INT_MAX));
 dp[rows][cols - 1] = 1;
 dp[rows - 1][cols] = 1;
 for (int i = rows - 1; i >= 0; i--) {
 for (int j = cols - 1; j >= 0; j--) {
 int minVal = min(dp[i + 1][j], dp[i][j + 1]);
 dp[i][j] = max(minVal - dungeon[i][j], 1);
 }
 }
 return dp[0][0];
 }
};