アルゴリズム・プログラミング誤り発見
動的計画法（dynamic programming）に関する記述のうち、誤っているものはどれか。
A.動的計画法は、部分問題の解を再利用することで計算量を削減する手法である。
✓ この記述は正しい。動的計画法は部分問題の重複を利用し、同一の計算を繰り返さないことが特徴である。
B.動的計画法が適用できる問題の条件の一つに、「最適部分構造」が挙げられる。
✓ この記述は正しい。最適部分構造とは、問題の最適解が部分問題の最適解から構成される性質のことである。
C.動的計画法とメモ化再帰は全く異なるアプローチであり、同じ問題に対して同一の結果を得ることはない。← 正解
✓ 正解です。この記述が誤りで、正しくはメモ化再帰はトップダウン型の動的計画法であり、同じ問題に対して同一の結果を得る。
D.フィボナッチ数列の計算に動的計画法を適用すると、単純な再帰に比べて計算量を大幅に削減できる。
✓ この記述は正しい。単純再帰のO(2^n)に対し、動的計画法を用いると O(n)に削減できる。