2次元の動的計画法まとめ 部分和問題編

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
  // 入力受け取り
  int64_t N, M;
  std::cin >> N >> M;
  std::vector<int64_t> A(N + 1);
  for (int64_t i = 1; i <= N; i++) {
    std::cin >> A.at(i);
  }

  // DPテーブル
  std::vector<std::vector<bool>> dp(N + 1, std::vector<bool>(M + 1, false));
  // 初期条件
  for (int64_t i = 0; i <= N; i++) {
    dp.at(i).at(0) = true;
  }

  // 遷移
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 1; j <= M; j++) {
      // i番目の要素を選ばないとき
      dp.at(i).at(j) = dp.at(i).at(j) || dp.at(i - 1).at(j);

      // i番目の要素を選ぶとき
      if (j - A.at(i) >= 0) {
        dp.at(i).at(j) = dp.at(i).at(j) || dp.at(i - 1).at(j - A.at(i));
      }
    }
  }

  // 出力
  if (dp.at(N).at(M)) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int main() {
  int64_t N, M;
  std::cin >> N >> M;
  std::vector<int64_t> A(N);
  std::vector<int64_t> B(N);
  for (int64_t i = 0; i < N; i++) {
    std::cin >> A.at(i) >> B.at(i);
  }

  // DPテーブル
  std::vector<std::vector<int64_t>> dp(N + 1, std::vector<int64_t>(M + 1, -1));
  // 初期条件
  dp.at(0).at(0) = 0;

  // 遷移
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 0; j <= M; j++) {
      if (dp.at(i - 1).at(j) >= 0) {
        // i番目の要素を使わずに済む場合
        dp.at(i).at(j) = B.at(i - 1);
      } else if (j < A.at(i - 1) || dp.at(i).at(j - A.at(i - 1)) <= 0) {
        // i番目の要素を何個使っても総和をちょうどjにできない
        dp.at(i).at(j) = -1;
      } else {
        // i番目の要素をいくつか使って総和をちょうどjにできる
        dp.at(i).at(j) = dp.at(i).at(j - A.at(i - 1)) - 1;
      }
    }
  }

  // 出力
  if (dp.at(N).at(M) >= 0) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}