動的計画法で文字列から別の文字列を拾い出す方法を数える

動的計画法 (DP)問題 140

文字列 s から、順番を変えずに文字を拾って文字列 t を作る拾い方が何通りあるかを数えます。t の前から何文字までを作ったかごとの数を、s の文字を 1 つずつ読みながら更新する練習です。

海外で定番の問題リスト 4 本には入っていません

問題

文字列 s と t を受け取ります。s から文字をいくつか選び、元の順番のままつなげると t になる選び方が何通りあるかを返す関数を書いてください。

選ぶ文字は隣どうしでなくてかまいません。s の中の場所の組が違えば、別の選び方として数えます
t が s から作れなければ 0 を返します
s と t の長さは 1 以上 1000 以下で、英小文字だけです
答えは 2^31 未満になるものとします。t の前から何文字かだけを作る数え方も、同じく 2^31 未満に収まるものとします

入力と出力の例

例 1

b は 0 番の 1 つです。a を 1 番から選ぶと n は 2 番か 4 番の 2 通り、a を 3 番から選ぶと n は 4 番の 1 通り、a を 5 番から選ぶと後ろに n がありません。合わせて 3 通りです。

s = "banana" t = "ban"

例 2

m は 2 番か 3 番、i は 4 番、t は 5 番か 6 番から選べるので、2 × 1 × 2 で 4 通りです。

s = "committee" t = "mit"

例 3

s の中で a は c より後ろにあるので、a、c、t の順には拾えません。

s = "cat" t = "act"

面接での聞かれ方

面接では、2 つの文字列を表の縦と横に取る動的計画の中でも、数え上げの難しい 1 問として出されます。

「s の部分列で t と等しくなる物は、いくつありますか」
最初に「同じ中身でも、拾う場所が違えば別に数えますか？」と確かめられるかを見られます
書き終えると「表を 1 行分に減らすとき、どちら向きに埋めますか？」と聞かれます

最長共通部分列の表と似ていますが、「最大」ではなく「足し算」で埋める点が違います。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

数学1-2 シグマと漸化式
CS2-9 動的計画法

まず考える手順

段 1

s の文字を使うか使わないかを全部試すと 2 の (s の長さ) 乗通りで、1000 文字では終わりません。

段 2

s の前から i 文字を使って、t の前から j 文字を作る選び方の数を ways[i][j] と置きます。s の i 文字目を使わない選び方は ways[i-1][j] 通りです。i 文字目が t の j 文字目と同じなら、それを最後の 1 文字に使う選び方が ways[i-1][j-1] 通り加わります。

段 3

t の前から 0 文字 (空) を作る選び方は、何も選ばない 1 通りです。なので ways[i][0] は全部 1 です。答えは ways[len(s)][len(t)] です。

段 4

s の文字を 1 つ読むごとに、使うのは 1 つ前の行だけです。t の長さ + 1 の並び 1 本を持ち、j を大きい方から小さい方へ書き換えます。小さい方から書き換えると、同じ s の文字を t の 2 か所に使う数え方が混ざってしまうからです。

解答

Python

def count_picks(s, t):
    n = len(t)
    w = [1] + [0] * n
    back = range(n, 0, -1)
    for ch in s:
        for j in back:
            if t[j - 1] != ch:
                continue
            w[j] += w[j - 1]
    return w[n]

JavaScript

function countPicks(s, t) {
  const n = t.length;
  const w = Array(n + 1)
    .fill(0);
  w[0] = 1;
  const back = [];
  for (let j = n; j > 0; j--) {
    back.push(j);
  }
  for (const ch of s) {
    for (const j of back) {
      if (t[j - 1] === ch) {
        w[j] += w[j - 1];
      }
    }
  }
  return w[n];
}

Go

func countPicks(
	s, t string,
) int {
	n := len(t)
	w := make([]int, n+1)
	w[0] = 1
	for i := 0; i < len(s); i++ {
		for j := n; j >= 1; j-- {
			if t[j-1] == s[i] {
				w[j] += w[j-1]
			}
		}
	}
	return w[n]
}

w[j] は、段 2 の表 ways[i][j] を 1 行に縮めた物で、ここまで読んだ s の文字で t の前から j 文字を作る選び方の数です。今の文字を使わない場合はそのまま残り、t の j 文字目と同じときだけ w[j-1] を足します。j を後ろから (back の順で) 回すので、足す w[j-1] はまだ今の文字を読む前の値です。

計算量

時間は O(m × n) です (m は s、n は t の長さ)。s の 1 文字ごとに t の長さだけ回ります。1000 文字どうしなら 100 万回です
使う記憶は O(n) です。持つのは 1 行分の並びだけです
2 次元の表をそのまま持つ書き方も時間は同じで、記憶が O(m × n) になります

よくある間違い

j を前から回す。 s = "a"、t = "aa" で、1 つの a を t の 1 文字目と 2 文字目の両方に使い、1 を返してしまいます。答えは 0 です
空の t を 0 通りにする。 w[0] を 0 にすると、どこからも数が増えず、答えがいつも 0 になります。何も選ばない 1 通りから始めます
同じ文字のときに「使う」だけを数える。文字が同じでも、使わない選び方は残ります。w[j] = w[j-1] と上書きすると、例 2 で後ろの t を選ぶ数え方が消えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def count_picks(s: str, t: str) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(count_picks("banana", "ban"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します