動的計画法（DP）における時間計算量と空間計算量の評価手法
1. 計算量評価の基本モデル
動的計画法（DP）の計算量を正確に見積もるためには、アルゴリズムを以下の3つの要素に分解して考えます。
状態（State）： dp[i] や dp[i][j] と定義される、部分問題の解を保持する変数。
状態の総数： 計算が必要なすべての部分問題の数（1次元DPなら $n$、2次元DPなら $n \times m$ など）。
遷移コスト： 1つの状態（例：dp ...
8月11日 09:02 投稿
動的計画法による部分列問題の徹底攻略：1次元・2次元、連続・非連続の各パターン
1. 不相交の線 (LeetCode 1035)
この問題は、一見すると幾何学的な制約があるように見えますが、本質的には「最長共通部分列 (LCS)」を求める問題と同じです。2つの配列間で線を引く際に交差させないという条件は、選ぶ要素の相対的な順序を維持することを意味します。
アルゴリズムの定義
dp[i][j] を、配列 data1 の最初の i 個の要素と、配列 data2 の最初の j 個の要 ...
7月7日 17:15 投稿
AtCoder Beginner Contest 358 全問題アプローチと実装例
A - Welcome to AtCoder Land
この問題では、入力された二つの文字列が特定の値と完全に一致するかを確認する基本的な処理が必要です。
実装ロジック
標準入力で受け取ったストリングスを入力変数へ保存し、固定されたターゲット文字列と比較します。両方が一致した場合のみ「Yes」を出力し、それ以外の場合は「No」を返却します。
#include <iostream>
#include & ...
5月17日 12:18 投稿