アルゴリズム設計において、状態遷移・貪欲選択・単調性・深さ優先探索の4つのパターンは頻出テーマです。以下にそれぞれの典型問題に対する実装手法と、構造化されたコード例を示します。

1. 取引手数料を含む株式利益の最大化

本問題は、状態を「保有中」と「未保有」に分類し、日次で利益が最大化される経路を追跡します。動的計画法を用いる場合、直前の状態から現在の状態へ遷移するコストを考慮します。また、貪欲法のアプローチでは、実質的な最低購入価格を管理し、閾値を超えた時点で利益を確定させることで計算量を削減できます。

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        # 動的計画法：状態マシンを用いた実装
        cash = 0                # 現金を保持（株を売却済み）
        hold = -prices[0]       # 株式を保有（購入済み）

        for price in prices:
            # 更新順序に注意：新しい cash を計算してから hold を更新
            new_cash = max(cash, hold + price - fee)
            new_hold = max(hold, cash - price)
            cash, hold = new_cash, new_hold
        return cash

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        # 貪欲法：実質コストを制御するアプローチ
        effective_buy_price = prices[0]
        total_gain = 0

        for current_price in prices:
            if current_price < effective_buy_price:
                effective_buy_price = current_price
            elif current_price > effective_buy_price + fee:
                total_gain += current_price - effective_buy_price - fee
                # 次回以降の買い値を調整（手数料分を相殺）
                effective_buy_price = current_price - fee
        return total_gain

2. 気温の上昇待ち日数算出（単調スタック）

配列内の各要素に対して、右側で初めて自分より大きい値が現れる位置を効率よく求める問題です。単調減少スタックを活用し、インデックスを保存します。現在の値がスタックの末尾より大きい場合、スタックから要素を取り出し、インデックスの差分を計算して結果配列に記録します。

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        result = [0] * len(temperatures)
        index_stack = []  # 温度が上昇する日を待つインデックスを保持

        for current_idx, current_temp in enumerate(temperatures):
            while index_stack and temperatures[index_stack[-1]] < current_temp:
                prev_idx = index_stack.pop()
                result[prev_idx] = current_idx - prev_idx
            index_stack.append(current_idx)
        return result

3. 株式価格の連続スパン算出

連続する過去の日数の中で、現在の価格以下であった日数をカウントします。単調減少スタックを用い、価格と同時にその価格が占めるスパン数をペアで保持します。現在の価格以上である過去のエントリをスタックから排出し、スパン数を累計することでクエリ応答を効率化します。

class StockSpanner:
    def __init__(self):
        # (価格, 連続日数) のタプルを保持するスタック
        self.history = [(float('inf'), 0)]

    def next(self, price: int) -> int:
        current_span = 1
        # 現在の価格以下の過去の記録を除去し、スパン数を合算
        while self.history[-1][0] <= price:
            current_span += self.history.pop()[1]
        self.history.append((price, current_span))
        return current_span

4. 電話番号の文字列全探索（バックトラッキング）

数字列に対応する文字の全組み合わせを生成する問題です。深さ優先探索（DFS）を用いて再帰的に文字を追加し、入力文字列の長さに達した時点で決定木の一つの経路を確定させます。探索状態の復元（バックトラック）を行わずに、引数としてパスを渡すことで状態管理を簡素化できます。

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        keypad = {
            '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
            '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"
        }
        combinations = []

        def explore(index: int, current_path: str) -> None:
            if index == len(digits):
                combinations.append(current_path)
                return

            for char in keypad[digits[index]]:
                explore(index + 1, current_path + char)

        explore(0, "")
        return combinations