🔄 DPアルゴリズム：最長逆背の順区間解析

📋 問題概要

n人が横一列に並んでおり、区間[l, r]内で身長が非増加（a[i] ≥ a[i+1]）になっている最長区間の長さを求める問題です。

入力例： heights = [187, 192, 115, 108, 109]
期待出力： 3（区間[1,3]: 192 → 115 → 108）

📊 入力データの視覚化

🧮 動的プログラミング解法

初期化
dp[0] = 1
遷移式適用
比較・更新
最大値取得
max(dp)
def find_longest_decreasing_interval_dp_optimized(n: int, heights: list[int]) -> int:
    """
    空間最適化版のDP解法
    
    Args:
        n (int): 人数
        heights (list[int]): 各人の身長のリスト
    
    Returns:
        int: 最長の逆背の順区間の長さ
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    max_length: int = 1  # 全体での最大長
    current_dp: int = 1  # dp[i]に相当（現在位置での最長区間長）
    
    for i in range(1, n):
        if heights[i-1] >= heights[i]:  # 非増加条件を満たす場合
            current_dp += 1  # 前の区間を延長
        else:
            current_dp = 1  # 新しい区間開始
        
        max_length = max(max_length, current_dp)
    
    return max_length

🔍 ステップバイステップ解析

ステップ i heights[i-1] heights[i] 条件 current_dp max_length

⚡ 計算量解析

⏱️ 時間計算量: O(n)
💾 空間計算量: O(1)
最適化ポイント：
  • DPテーブル全体を保持せず、必要な状態のみ記録
  • 一回のスキャンで最適解を取得
  • メモリ使用量を定数に抑制

🎯 3つのDP手法比較

# 手法1: 基本DP（配列版）
def basic_dp(n: int, heights: list[int]) -> int:
    dp = [1] * n  # O(n)空間
    for i in range(1, n):
        if heights[i-1] >= heights[i]:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = 1
    return max(dp)

# 手法2: 空間最適化版（推奨）
def optimized_dp(n: int, heights: list[int]) -> int:
    max_length, current_dp = 1, 1  # O(1)空間
    for i in range(1, n):
        if heights[i-1] >= heights[i]:
            current_dp += 1
        else:
            current_dp = 1
        max_length = max(max_length, current_dp)
    return max_length

# 手法3: 全区間DP（参考用）
def all_intervals_dp(n: int, heights: list[int]) -> int:
    dp = [[False] * n for _ in range(n)]  # O(n²)空間
    # 全区間を2重ループで確認 O(n²)時間
    # ...