【Rust】最短経路問題

M, N = 6, 5

route = [[0 for i in range(N + 1)]for j in range(M + 1)]

print(route)

$ python3 test.py
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

↓

fn main() {
    let M = 6;
    let N = 5;

    let mut route: Vec<Vec<usize>> = Vec::new();
    
    for _ in 0..(M+1) {
        let mut L: Vec<usize> = Vec::new();
        for _ in 0..(N+1) {
            L.push(0);
        } 
        route.push(L);
    }
    println!("{:?}", route);
}

[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

fn main() {
    let M = 6;
    let N = 5;

    let mut route: Vec<Vec<usize>> = Vec::new();
    
    for _ in 0..(M+1) {
        let mut L: Vec<usize> = Vec::new();
        for _ in 0..(N+1) {
            L.push(0);
        } 
        route.push(L);
    }

    for i in 0..(M+1){
        route[i][0] = 1;
    }
    
    for i in 1..(N+1) {
        route[0][i] = 1;
        for j in 1..(M+1) {
            route[j][i] = route[j - 1][i] + route[j][i - 1];
        }
    }
    println!("{:?}", route);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
[[1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6], [1, 3, 6, 10, 15, 21], [1, 4, 10, 20, 35, 56], [1, 5, 15, 35, 70, 126], [1, 6, 21, 56, 126, 252], [1, 7, 28, 84, 210, 462]]

おおお、なるほど、これは凄い。

実はこう書ける

fn search(m: usize, n: usize) -> usize {
    if (m == 0) || (n == 0) {
        return 1
    }

    return search(m-1, n) + search(m, n - 1);
}

fn main() {
    let M = 6;
    let N = 5;

    println!("{}", search(M, N));
}

なるほど、これは凄い。
経路の問題も基本は、位置を数字で表現するのね。