「01ナップサック」
$N$ 個の品物にはそれぞれ「重さ($w_{i}$) 」と「価値($v_{i}$)」というパラメータがあります。
今、これらの品物からいくつか取り出そうとします。
重さの合計が $W$ 以下になっていれば、どう取り出してもいいです。
価値が最大にできる取り出しかたを選んだとき、その価値を求めてください。

#include <iostream>
#include <algorithm>
using namespace std;

int main(void) {
  int N; scanf("%d", &N);
  vector<int> w(N), v(N);
  for(int i=0; i<N; i++) { scanf("%d", &w[i]); }
  for(int i=0; i<N; i++) { scanf("%d", &v[i]); }
  int W; scanf("%d", &W);
  vector<vector<int>> dp(N+1, vector<int>(W+1));
  // i番目を取るか取らないか悩んでいる状態。
  // 今までの重さはj。
  for(int i=0; i<N; i++) {
    for(int j=0; j<=W; j++) {
      // i番目を取らない。
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
      // i番目を取っても重さがW以下でおさまるならi番目を取れるので、取る。
      // i番目を取ると重さはj+w[i]になり、価値はdp[i][j]からv[i]だけ増える。
      if(j + w[i] <= W) {
        dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i]);
      }
    }
  }
  int res = dp[N][W];
  printf("%d\n", res);
  return 0;
}
      

HPが $H$ の化け猫を倒すことを考えます。
与ダメージ $A$ の通常攻撃は必ずヒットしますが、与ダメージ $D$ の必殺攻撃は $2/3$ の確率でしか成功せず、失敗したときはダメージを与えられません。
毎回どちらかの攻撃をしたとして、化け猫を倒すまでに攻撃する回数の期待値を最小とするように攻撃していったとき、倒したときの攻撃回数の期待値はいくらですか。yukicoder No.23
$H, A, D$ はともに $10{,}000$ 以下。
答えへのリンク

お寿司が $N$ 皿あります。それぞれが美味しさをパラメータとして持っています。
連続したお皿を取れないというルールがある中で、美味しさの合計を最大にするようにお寿司を取ったとき、その美味しさはいくらになりますか。yukicoder No.45
$N$ は $1{,}000$ 以下。それぞれの美味しさは $100$ 以下。
答えへのリンク

天秤に $N$ 個のおもりを置くことを考えます。
おもりは必ず左右のどちらかに置くとしたとき、天秤が釣り合うようにできるかを判定してください。yukicoder No.4
$N$ は $100$ 以下。それぞれのおもりの重さも $100$ 以下。
答えへのリンク

$N$ 問の問題について、それぞれの配点が与えられます。
総得点として取り得るのは何通りか求めてください。AtCoder Typical DP A
$N$ は $100$ 以下。各問の配点も $100$ 以下。
答えへのリンク

こんな2人対戦のゲームをします。
猫コインが積まれた山が2つあり、先手と後手が交互にどちらかの山の一番上の猫コインを取ります。
猫コインにはそれぞれ価値がパラメータとして存在し、両者とも取ったコインの合計価値をなるべく多くしたいとします。
どっちかの山からコインが無くなったら、残ってる方の山から取ります。
どっちの山からもコインが無くなったらゲーム終了です。先手が得る価値の合計はいくらですか。AtCoder Typical DP B
ひとつの山に積まれた猫コインの数は $1{,}000$ 以下。猫コインの価値も $1{,}000$ 以下。
答えへのリンク

敵が最大で3体いて、それぞれのHPが与えられます。
全体攻撃をすることができ、1体めは $9$ ポイント、2体めは $3$ ポイント、3体めは $1$ ポイントのダメージを与えることができます。
全体攻撃をするとき、敵をどの順番で攻撃してもいいとすると、最低何ターンで全ての敵を倒すことができますか。SRM 658 Div2 Med
それぞれのHPは $60$ 以下。
答えへのリンク