動的プログラミングによる問題解決：フィボナッチ数、階段の登り方、最小コストでの階段登り
動的プログラミング問題へのアプローチ
動的プログラミング問題を解決するための5つのステップ：
DP配列（DPテーブル）とそのインデックスの意味を定義する
漸化式を決定する
DP配列の初期化方法を決定する（配列オーバーフローに注意）
計算順序を決定する
DP配列の具体例を導出する
フィボナッチ数
フィボナッチ数列（通常 F(n) で表される）は、0 と 1 から始まり、そ ...
6月24日 21:13 投稿
行列高速累乗による線形漸化式の効率的解法
線形漸化式（例：フィボナッチ数列）を単純に計算すると、nが10⁸を超えると時間がかかりすぎます。これを解決するのが「行列高速累乗」です。この手法は、二進展開と行列乗算を組み合わせ、計算量をO(log n)まで削減します。
基礎知識：二進高速累乗
整数のべき乗を高速に計算するアルゴリズムです。指数を二進数で分解し、繰り返し二乗しながら結果を構築します。
long l ...
6月24日 01:05 投稿
Codeforces Round 998 (Div.3) 解説: A-D問題の解法と実装例
コンテスト参加後の復習と解法の整理を行います。問題AからDまでのアプローチとコードをまとめました。
A. Fibonacciness
5要素の数列における最大の「フィボナッチ度」を求める問題です。数列の長さが5であるため、最大でも度は3となります。各位置で成立するフィボナッチ関係の式を検討します。
具体的には、a0+a1 = a2、a1+a2 = a3、a2+a3 = a4の3つの条件が考えら ...
6月22日 17:44 投稿
Pythonでフィボナッチ数列を応用した階段の登り方を求解する
問題概要と考察
この問題では、n段の階段を1段または2段ずつ登る場合の、登り方の総数を求める必要があります。各段数における解を観察すると、フィボナッチ数列と同じパターンに従っていることが分かります。
1段：1通り
2段：2通り（1+1 または 2）
3段：3通り（1+1+1、1+2、2+1）
4段：5通り（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）
つまり、n段目までの登り方の総数 ...
5月14日 19:00 投稿