[AtCoder] ABC 087 C – Candies

問題

方針

動的計画法

\( dp[i][j] \) をマス \( (i, j)\) におけるアメの所持数の最大値とします。マスの移動は右か下に行くかだけなので、下に行くことができるのは \( 1 \) 回だけとなります。したがって、

\[ dp[0][j] = dp[0][j – 1] + A[0][j]\]

が成り立ちます。これは最初からずっと右方向に移動してアメを回収していくことを意味します。\( B[1][j]\) については、次の更新式を適用します。

\[B[1][j] = A[1][j] + \max (B[1][j – 1],\ B[0][j]) \]

これは、マス \( (1, j) \) への行き方が左から来るのか、上から来るかの2通りだからです。したがって、\( B[1][N – 1]\) が解答になります。

コード

提出したコード

動的計画法

  int dp[2][N];
  dp[0][0] = A[0][0];
  dp[1][0] = A[0][0] + A[1][0];
  for (int i = 1; i < N; i++) {
    dp[0][i] = dp[0][i - 1] + A[0][i];
    dp[1][i] = max(dp[0][i], dp[1][i - 1]) + A[1][i];
  }