問題概要 ２つの文字列t, sが与えられる。 これら２つの共通部分文字列の長さの最大値を求めよ。 共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、 順序は等しくなければならない。 例示 s = "abcd" t = "becd"LCS = 3 (…

問題概要 フィボナッチ数列の総和を返す 解法 1.メモ化 /* メモfb[]はあらかじめ-1(メモ無し)で初期化する */ fib(int a){ /* メモ化チェック */ if(fb[a] != -1 ) return fb[a]; if( a == 0 ) ret = 0; else if( a == 1 ) ret = 1; else ret = fib(a-1) + f…

問題概要 重さwと価値vがついた品物がn個ある。 これらの品物から、重さの総和がWを超えないように選んだときの 価値の総和の最大値を求めなさい。 問題解法 1.全探索 再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。 重さの総…

問題概要 とても長い板からN個の板を切り出す。 切り出す板はL1,L2,...Lnであり、元の板の合計となっている。 板を切断する際に、その板の長さだけコストがかかる。 例えば２１の板を１３と８に分けた場合、コストは13+8である。 最小コストで板を切り出した…

サイコロの期待値 期待値 期待値は「確率で重み付けした値の和」。*1 例題*2 アリスがa面サイコロ、ボブがb面サイコロを持っている。 単純に出た目が多い方が勝ちというゲームを行う。 アリスが勝つことを知っているとき、アリスが出す出目の期待値を求めよ…

問題概要 入力：整数集合 出力：整数値 整数集合の冪集合を抽出し、その合計値を算出せよ。 ただし、冪集合は隣り合う値でのみ採用する。 {1, 2, 3} ▶︎{ 1 }, { 2 }, { 3 }, {1, 2}, {2, 3}, { 1, 2, 3} ▶︎1, 2 ,3, 3, 5, 6 ▶︎20 class SumOfPower { public …