最小コスト弾性マッチング問題

問題

dp[0][0] = 0 だが c[0][0] = 0 ではない

// 入力
int N, M;
int C[110][110];

// DP テーブル
int dp[110][110]; //[a : i番目][b : j番目]

int main() {
  cin >> N >> M; //aの個数、bの個数
  for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> C[i][j]; //コスト
  
  // 初期化
  for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) dp[i][j] = INF;
  dp[0][0] = 0;

  // ループ
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      //if (i+1 <= N) //aの個数内
        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + C[i][j]); //aのみ進める
      //if (j+1 <= M) //bの個数内
        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + C[i][j]); //bのみ進める
      //if (i+1 <= N && j+1 <= M) //aの個数内 && bの個数内
        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + C[i][j]); //どちらも進める
    }
  }

  cout << dp[N][M] << endl;
}