メモ化について、僕の解釈〜メモ化とDPの違い(?)〜
そもそも、メモ化はDPに含まれるようです。
多分。
そして、これはフィボナッチ数を出すプログラムですが、
#include<iostream> #include<algorithm> #define N 9 using namespace std; int t[N]; int fib(int n){//メモ化? if(n <= 1)return 1; int sum = 0; int a = t[n-1], b = t[n-2]; if(a == -1)a = fib(n-1); if(b == -1)b = fib(n-2); t[n-1] = a; t[n-2] = b; return a + b; } main(){ fill(t, t+N, -1); cout << fib(N-1) << endl; int dp[N]; dp[0] = dp[1] = 1; for(int i=2; i<N; i++){ dp[i] = dp[i-1] + dp[i-2];//普通のDP? } cout << dp[N-1] << endl; }
こういうことでしょうか?
批判など意見お待ちしております。