题解 | 精灵鼠从入口到出口的最少减少速度

use std::io::{self, *};

fn main() {
    let mut stdin = io::stdin();
    let mut input = String::new(); 
    stdin.read_to_string(&mut input).unwrap();
    let mut lines = input.split_whitespace();

    let n = lines.next().unwrap().parse::<usize>().unwrap();
    let mut my = vec![Vec::new();n];
    let mut dp = vec![vec![i32::MAX; n];n];
    for i in 0..n {
        let line = lines.next().unwrap().split(',');
        for val in line {
            my[i].push(val.parse::<i32>().unwrap());
        }
    }
    // println!("{:?}", my);
    if n == 1 { print!("{}", my[0][0]); return; }
    dp[0][0] = my[0][0];
    for i in 0..n {
        for j in 0..n {
            if i + 1 < n {
                dp[i + 1][j] = dp[i + 1][j].min(my[i + 1][j] + dp[i][j]);
            }
            if j + 1 < n {
                dp[i][j + 1] = dp[i][j + 1].min(my[i][j + 1] + dp[i][j]);
            }
        }
    }
    //println!("{:?}", dp);
    print!("{}", dp[n - 1][n - 1]);
}