June 10, 2022: Captain Shu crosses a sweet potato field from north to South (m long from north to South and N wide from east to West). The sweet potato field is divided into 1x1 squares. He can start

2022-06-10： The potato captain crosses a sweet potato field from north to south （ North and South length M, East-West width N）, The sweet potato field is divided into 1x1 Of the lattice ,
He can start from any grid in the North , Get to any grid in the South ,
But each step can only go to the southeast 、 due south 、 One of the three grids in the southwest ,
And you can't step out of the sweet potato field , He can get all the sweet potatoes on the grid , How many sweet potatoes can he get .
From little red book , The first question in the little red book .

answer 2022-06-10：

Dynamic programming .dp It's a two-line grid .dp[0] It's plus arr[i][j] Array of previous maximum values .dp[1] It's plus arr[i][j] After that, the maximum value array .
dp[1][j]=arr[i][j]+max(dp[0][j-1],dp[0][j],dp[[0][j+1]). The future is uncertain , But the past is certain .dp[0] For the past ,dp[1] Select the best direction according to the past three directions .
Time complexity ：O(MN).
Spatial complexity ：O(N). Occupy two rows of cells .

The code to use rust To write . The code is as follows ：

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];
    }
    //  Keep counting ！
    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;
}

//  Optimal method 
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
    }
}

The results are as follows ：

---

Zuo Shen java Code