「動的計画法」の版間の差分

==== 定義を直接実装したプログラム ====

定義に基づいてプログラムを作成すると、次のようになる。

int fib(unsigned int n) {

switch (n) {

 

====動的計画法を利用したプログラム（ボトムアップ方式）====

int fib(unsigned int n) {

int memo[1000] = {0, 1}, i;

====動的計画法を利用したプログラム（トップダウン方式）====

トップダウンで、[[メモ化]]を併用したやり方。fib(n) を計算するのに、fib(n - 1) と fib(n - 2) が必要だが、計算結果を配列 memo に保存して再利用している。

#include <stdbool.h>

 

近年は色々な[[プログラミング言語]]が[[メモ化]]を言語レベルでサポートしている。その機能を利用した場合、より簡単に書ける場合がある。例えば [[Groovy]] の場合、@Memoized を付けることでメモ化するが、下記のように、定義を直接実装したプログラムに @Memoized を付けると動的計画法になる。

 

import groovy.transform.Memoized