Rustで動的計画法 (5)

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。5章の動的計画法。

前回 → https://quantized-cube.com/rust-dp-04

今回は区間分割。

use proconio::input;

fn input(use_default_values: bool) -> (usize, Vec<Vec<i64>>) {
    if use_default_values {
        let n: usize = 3;
        let c: Vec<Vec<i64>> = vec![
            vec![0, 2, 3, 5],
            vec![0, 0, 2, 5],
            vec![0, 0, 0, 1],
            vec![0, 0, 0, 0],
        ];
        return (n, c);
    } else {
        println!("Input n and c:");
        input! {
            n: usize,
            c: [[i64; n+1]; n+1],
        }
        return (n, c);
    }
}

const INF: i64 = 1 << 60; // 十分大きな値 (ここでは 2^60 とする)

fn chmin<T: PartialOrd>(a: &mut T, b: T) {
    if *a > b {
        *a = b;
    }
}

/// 区間ごとに分割する方法を最適化する
pub fn code_5_9(use_default_values: bool) -> i64 {
    // 入力
    let (n, c) = input(use_default_values);

    // DP テーブル定義
    let mut dp = vec![INF; n + 1];

    // DP 初期条件
    dp[0] = 0;

    // DPループ
    for i in 0..=n {
        for j in 0..i {
            let b = dp[j] + c[j][i];
            chmin(&mut dp[i], b);
        }
    }

    // 答えの出力
    dp[n]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn code_5_8_works() {
        let result = code_5_9(true);
        assert_eq!(result, 4);
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust