# APCS實作題2020年10月第3題：勇者修煉

> 日期：2024年7月11日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f314)

## 題目

### 問題描述

輸入為 $m \times n$ 大小的的陣列，每一格是一個介於 $-100$ 與 $100$ 之間的整數，表示經過這格可以累積的經驗值。你可以從最上面一排任何一個位置開始，在最下面一排任何一個位置結束。過程中每一步可以選擇往左、往右或往下走，但不能走回已經經過的位置。請你算出最多可以獲得的經驗值總和（可能是負數）。
<br />

### 輸入說明

第一行有兩個正整數 $m, n ~(1 \leq m \leq 50,~ 1 \leq n \leq 10000)$。
接下來 $m$ 行，每行包含 $n$ 個整數。第 $i$ 行的第 $j$ 個數字表示在 $(i, j)$ 位置可以得到的經驗值。

配分
- 20%：$n \leq 100,~ m=1$
- 30%：$n \leq 100$
- 50%：$n \leq 10000$

<br />

### 輸出格式

輸出可以獲得的最多經驗值總和。
<br />

### 範例輸入

1 5
2 1 4 -7 4

### 範例輸出

7

<br />

## Python 程式碼

### 寫法1，用 $m \times n$ 串列儲存走到位置 (r, c) 的最大經驗值

比較容易理解的寫法，會使用比較多的記憶體。費時最久約為 0.9 s，使用記憶體最多約為 17.6 MB，通過測試。

m, n = map(int, input().split())  # 讀取地圖列數 m、欄數 n
dp = [[0]*n for _ in range(m)]  # dp[r][c]，走到 (r, c) 位置的最大經驗值
lmax = [0]*n  # 由左向右走到第 c 欄的最大經驗值
rmax = [0]*n  # 由右向左走到第 c 欄的最大經驗值
pos = list(map(int, input().split()))  # 一次讀一列地圖資料
""" 先處理第 0 列 """
# 由左向右走
lmax[0] = pos[0]  # 先處理位置 0
for c in range(1, n):  # 處理 1 ~ n-1，只能往右走
    lmax[c] = max(lmax[c-1], 0) + pos[c]  # 取 lmax[c-1], 0 較大者加上 pos[c] 
# 由右向左走
rmax[n-1] = pos[n-1]  # 先處理位置 n-1
for c in range(n-2, -1, -1):  # 處理 n-2 ~ 0，只能往左走
    rmax[c] = max(rmax[c+1], 0) + pos[c]  # 取 rmax[c+1], 0 較大者加上 pos[c] 
# 取出 lmax[c], rmax[c] 較大者存到 dp[0][c]
for c in range(n):
    dp[0][c] = max(lmax[c], rmax[c])
""" 再處理第 1 ~ m-1 列 """
for r in range(1, m):  # 重複 m-1 次
    pos = list(map(int, input().split()))  # 一次讀一列地圖資料
    # 由左向右走
    lmax[0] = dp[r-1][0] + pos[0]  # 先處理位置 0，只能由上往下走
    for c in range(1, n):  # 處理 1 ~ n-1，取往下走、往右走總合較大者
        lmax[c] = max(dp[r-1][c], lmax[c-1]) + pos[c]
    # 由右向左走
    rmax[n-1] = dp[r-1][n-1] + pos[n-1]  # 先處理位置 0，只能由上往下走
    for c in range(n-2, -1, -1):  # 處理 n-2 ~ 0，取往下走、往左走總合較大者
        rmax[c] = max(dp[r-1][c], rmax[c+1]) + pos[c]
    # 取出 lmax[c], rmax[c] 較大者存到 dp[r][c]
    for c in range(n): dp[r][c] = max(lmax[c], rmax[c])
""" end of for loop """
ans = max(dp[m-1])  # 取最大值
print(ans)  # 印出答案

<br /><br />

### 寫法2，用二維串列記錄每一格最大、向右、向左走的經驗值

由於 dp 串列裡的值會不斷蓋掉，改成這一列對應的值，比較難讀懂程式碼。費時最久約為 0.9 s，使用記憶體最多約為 8.3 MB，通過測試。

m, n = map(int, input().split())  # 讀取地圖列數 m、欄數 n
# dp[c]，以第c欄作為終點的最大經驗值，資料為 [兩種走法的最大值, 由左向右走, 由右向左走]
dp = [[0]*3 for _ in range(n)]
""" 主要的解題過程 """
for r in range(m):  # 重複 m 次
    pos = list(map(int, input().split()))  # 一次讀一列地圖資料
    # 由左向右走
    dp[0][1] = dp[0][0] + pos[0]  # 先處理位置 0，只能由上往下走
    for c in range(1, n):  # 處理 1 ~ n-1，取往下走、往右走總合較大者
        dp[c][1] = max(dp[c][0] + pos[c], dp[c-1][1] + pos[c])
    # 由右向左走
    dp[n-1][2] = dp[n-1][0] + pos[n-1]  # 先處理位置 n-1，只能由上往下走
    for c in range(n-2, -1, -1):  # 處理 (r, n-2) ~ (r, 0)，取往下走、往左走總合較大者
        dp[c][2] = max(dp[c][0] + pos[c], dp[c+1][2] + pos[c])
    # 取出 dp[c][1], dp[c][2] 的最大值存到 dp[c][0]
    for d in dp: d[0] = max(d[1], d[2])
""" end of for loop """
ans = max([d[0] for d in dp])  # 取最大值
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，用 $m \times n$ 陣列儲存走到位置 (r, c) 的最大經驗值

比較容易理解的寫法，會使用比較多的記憶體。費時最久約為 40 ms，使用記憶體最多約為 1.6 MB，通過測試。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int m, n; cin >> m >> n;  // 讀取地圖列數 m、欄數 n
    vector<vector<int>> dp (m, vector<int> (n, 0));  // dp[r][c]，走到 (r, c) 位置的最大經驗值
    vector<int> lmax (n, 0), rmax (n, 0), pos (n, 0);  // 分別為由左向右、由右向左走到第 c 欄的最大經驗值，地圖經驗值
    for(int c=0; c<n; c++) cin >> pos[c];  // 讀取一列地圖資料
    /* 先處理第 0 列 */
    // 由左向右走
    lmax[0] = pos[0];  // 先處理位置 0
    for(int c=1; c<n; c++)  // 處理 1 ~ n-1，只能往右走
        lmax[c] = max(lmax[c-1], 0) + pos[c];  // 取 lmax[c-1], 0 較大者加上 pos[c] 
    // 由右向左走
    rmax[n-1] = pos[n-1];  // 先處理位置 n-1
    for(int c=n-2; c>=0; c--)  // 處理 n-2 ~ 0，只能往左走
        rmax[c] = max(rmax[c+1], 0) + pos[c];  // 取 rmax[c+1], 0 較大者加上 pos[c] 
    // 取出 lmax[c], rmax[c] 較大者存到 dp[0][c]
    for(int c=0; c<n; c++) dp[0][c] = max(lmax[c], rmax[c]);
    /* 再處理第 1 ~ m-1 列 */
    for(int r=1; r<m; r++) {  // 重複 m-1 次
        for(int c=0; c<n; c++) cin >> pos[c];  // 讀取一列地圖資料
        // 由左向右走
        lmax[0] = dp[r-1][0] + pos[0];  // 先處理位置 0，只能由上往下走
        for(int c=1; c<n; c++)  // 處理 1 ~ n-1，取往下走、往右走總合較大者
            lmax[c] = max(dp[r-1][c], lmax[c-1]) + pos[c];
        // 由右向左走
        rmax[n-1] = dp[r-1][n-1] + pos[n-1];  // 先處理位置 0，只能由上往下走
        for(int c=n-2; c>=0; c--)  // 處理 n-2 ~ 0，取往下走、往左走總合較大者
            rmax[c] = max(dp[r-1][c], rmax[c+1]) + pos[c];
        // 取出 lmax[c], rmax[c] 較大者存到 dp[r][c]
        for(int c=0; c<n; c++) dp[r][c] = max(lmax[c], rmax[c]);
    }
    
    int ans = *max_element(dp[m-1].begin(), dp[m-1].end());  // 取最大值
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，用二維陣列記錄每一格最大、向右、向左走的經驗值

由於 dp 串列裡的值會不斷蓋掉，改成這一列對應的值，比較難讀懂程式碼。費時最久約為 42 ms，使用記憶體最多約為 772 kB，通過測試。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int m, n; cin >> m >> n;  // 讀取地圖列數 m、欄數 n
    // dp[c]，以第c欄作為終點的最大經驗值，資料為 [兩種走法的最大值, 由左向右走, 由右向左走]
    vector<int> pos (n, 0);
    vector<vector<int>> dp (n, vector<int> (3, 0));
    /* 主要的解題過程 */
    for(int r=0; r<m; r++) {  // 重複 m 次
        for(int c=0; c<n; c++) cin >> pos[c];  // 一次讀一列地圖資料
        // 由左向右走
        dp[0][1] = dp[0][0] + pos[0];  // 先處理位置 0，只能由上往下走
        for(int c=1; c<n; c++)  // 處理 1 ~ n-1，取往下走、往右走總合較大者
            dp[c][1] = max(dp[c][0] + pos[c], dp[c-1][1] + pos[c]);
        // 由右向左走
        dp[n-1][2] = dp[n-1][0] + pos[n-1];  // 先處理位置 n-1，只能由上往下走
        for(int c=n-2; c>=0; c--)  // 處理 (r, n-2) ~ (r, 0)，取往下走、往左走總合較大者
            dp[c][2] = max(dp[c][0] + pos[c], dp[c+1][2] + pos[c]);
        // 取出 dp[c][1], dp[c][2] 的最大值存到 dp[c][0]
        for(int c=0; c<n; c++)
            dp[c][0] = max(dp[c][1], dp[c][2]);
    }
    // 取最大值
    int ans = dp[0][0];
    for(int c=1; c<n; c++)
        ans = max(ans, dp[c][0]);
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`