問題
目標の数字Sが与えられる。初めは1からスタートし、以下の操作を行い目標の値にする。
- 現在の値をコピー
- 以前コピーした値を現在の値に加算
- 現在の値から1を引く
Sとするのに必要となる最小の操作回数を求めよ。
解法1
1を引く操作ができないと仮定すると、現在の値とコピーした値で全探索をすることができる。
この時の計算量を計算する。
このあとに、1を引いた方が少ない回数となる箇所を探索する。1が引けなくなるまで以上の操作を繰り返すことで答えが求まる。Nを上回ることはないのでとするが、実際はかなり小さい回数で停止する。
計算量1
時間計算量:
空間計算量:
コード1
解法2
現在の値とコピーした値をメモ化し動的計画法で解く。sを現在の値、cをコピーした値とし、状態を(s, c)で表す。はじめ、(1, 0)からスタートしBFSで最小の操作回数を求める。
計算量2
時間計算量:
空間計算量: