IT｜２項間漸化式の問題を解いてみた。２項間とは、aの1がxの時、aのnは何であるか。

２項間漸化式とは？

２項：隣り合う２つの項つまり（anとan+1)という２つの項。

漸化式：前の項を使って次の項を求める式。

数列の出現パターンを次の値は何か？という漸化式を使って求めるタイプの問題のことを解決する手段のことをそう呼ぶらしい。等差数列や等比数列は漸化式の他に公式があるっぽいので、今回のアルゴリズムは実用的ではないがDP（動的計画法）を学ぶには必要な知識ということで問いてみた。

イマイチ、どういう頭の使い方をしたら漸化式が見つかるのかわからない。それはつまりDPをどういうイメージで実装すれば良いか分からないから学習しているわけだが。これを積み重ねれば本当にわかるようになるのだろうか。

たぶんaの1、aの2、aの3…だからaのnは…って感じで紙に書き出していくしかないのだと思う。今回は疑似コードをそのままphp言語でプログラミングしただけだが、最近書いてないので文法を思い出すのに一苦労だった。

<?php
    $in = fgets(STDIN);
    $ar = array();
    $ar = explode(' ', $in);
    
    // echo $ar[0]."\n";
    // echo $ar[1]."\n";
    // echo $ar[2]."\n
    
    $x = $ar[0];
    $d = $ar[1];
    $k = $ar[2];
    $a = array();
    $a[0] = $ar[0];
    
    for($i = 1; $i <= $k; $i++){
        $a[$i] = $a[($i - 1)] + $d;
    }
    
    // print_r($a);
    echo $a[($k - 1)];
?>