Rustで動的計画法 (1)

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

必要なら proconio を cargo add しておく。

use proconio::input;
use std::cmp;

const INF: i64 = i64::MAX;

fn input(use_default_values: bool) -> (usize, Vec<i64>) {
    if use_default_values {
        let n: usize = 7;
        let h: Vec<i64> = vec![2, 9, 4, 5, 1, 6, 10];
        return (n, h);
    } else {
        println!("Input n and h:");
        input! {
            n: usize,
            h: [i64; n],
        }
        return (n, h);
    }
}

pub fn code_5_1(use_default_values: bool) -> i64 {
    // 入力
    let (n, h) = input(use_default_values);

    // 配列 dp を定義 (配列全体を無限大を表す値に初期化)
    let mut dp = vec![INF; n];

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

    // ループ
    for i in 1..n {
        if i == 1 {
            dp[i] = (h[i] - h[i - 1]).abs()
        } else {
            dp[i] = cmp::min(
                dp[i - 1] + (h[i] - h[i - 1]).abs(),
                dp[i - 2] + (h[i] - h[i - 2]).abs(),
            );
        }
    }

    // 答え
    return dp[n - 1];
}


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

    #[test]
    fn code_5_1_works() {
        let result = code_5_1(true);
        assert_eq!(result, 8);
    }
}

今回はここまで。

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