2022-06-10：薯队长从北向南穿过一片红薯地（南北长M，东西宽N），红薯地被划分为1x1的方格，他可以从北边的任何一个格子

fn main() {
    let mut map: Vec<Vec<i32>> = vec![
        vec![3, 5, 6, 2, 4],
        vec![7, 8, 9, 1, 1],
        vec![1, 2, 3, 4, 5],
    ];
    let ans = max_score(&mut map);
    println!("ans = {}", ans);
    let mut map: Vec<Vec<i32>> = vec![
        vec![3, 5, 6, 2, 4],
        vec![7, 8, 9, 1, 1],
        vec![1, 2, 3, 4, 5],
    ];
    let ans = max_score2(&mut map);
    println!("ans = {}", ans);
    let mut map: Vec<Vec<i32>> = vec![
        vec![3, 5, 6, 2, 4],
        vec![7, 8, 9, 1, 1],
        vec![1, 2, 3, 4, 5],
    ];
    let ans = max_score3(&mut map);
    println!("ans = {}", ans);
}

fn max_score(map: &mut Vec<Vec<i32>>) -> i32 {
    let mut ans = 0;
    for col in 0..map[0].len() as i32 {
        ans = get_max(ans, process(map, 0, col));
    }
    return ans;
}

fn process(map: &mut Vec<Vec<i32>>, row: i32, col: i32) -> i32 {
    if col < 0 || col == map[0].len() as i32 {
        return -1;
    }
    if row == map.len() as i32 - 1 {
        return map[row as usize][col as usize];
    }
    let cur = map[row as usize][col as usize];
    let next1 = process(map, row + 1, col - 1);
    let next2 = process(map, row + 1, col);
    let next3 = process(map, row + 1, col + 1);
    return cur + get_max(get_max(next1, next2), next3);
}

fn max_score2(map: &mut Vec<Vec<i32>>) -> i32 {
    let mut ans = 0;
    let n = map.len() as i32;
    let m = map[0].len() as i32;
    let mut dp: Vec<Vec<i32>> = vec![];
    for i in 0..n {
        dp.push(vec![]);
        for _ in 0..m {
            dp[i as usize].push(-2);
        }
    }
    for col in 0..map[0].len() as i32 {
        ans = get_max(ans, process2(map, 0, col, &mut dp));
    }
    return ans;
}

fn process2(map: &mut Vec<Vec<i32>>, row: i32, col: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if col < 0 || col == map[0].len() as i32 {
        return -1;
    }
    if dp[row as usize][col as usize] != -2 {
        return dp[row as usize][col as usize];
    }
    // 继续算！
    let mut ans = 0;
    if row == map.len() as i32 - 1 {
        ans = map[row as usize][col as usize];
    } else {
        let cur = map[row as usize][col as usize];
        let next1 = process2(map, row + 1, col - 1, dp);
        let next2 = process2(map, row + 1, col, dp);
        let next3 = process2(map, row + 1, col + 1, dp);
        ans = cur + get_max(get_max(next1, next2), next3);
    }
    dp[row as usize][col as usize] = ans;
    return ans;
}

// 最优方法
fn max_score3(map: &mut Vec<Vec<i32>>) -> i32 {
    let n = map.len() as i32;
    let m = map[0].len() as i32;
    let mut dp: Vec<Vec<i32>> = vec![];
    for _ in 0..2 {
        dp.push(map[0].clone());
    }

    for i in 1..n {
        for j in 0..m as i32 {
            dp[1][j as usize] = get_max(
                get_max(
                    dp[0][j as usize],
                    if j - 1 >= 0 {
                        dp[0][(j - 1) as usize]
                    } else {
                        0
                    },
                ),
                if j + 1 < m {
                    dp[0][(j + 1) as usize]
                } else {
                    0
                },
            ) + map[i as usize][j as usize];
        }
        dp[0] = dp[1].clone();
    }

    let mut ans = dp[0][0];
    for i in 1..m {
        ans = get_max(ans, dp[0][i as usize]);
    }

    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}