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

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cin.ignore(); // 忽略换行符
    
    // 读入数据
    vector<vector<int>> num(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        stringstream ss(line);
        string temp;
        int j = 0;
        while(getline(ss, temp, ',')) {
            num[i][j++] = stoi(temp);
        }
    }
    
    // 动态规划数组
    vector<vector<int>> dp(n, vector<int>(n));
    dp[0][0] = num[0][0];
    
    // 初始化第一行和第一列
    for(int i = 1; i < n; i++) {
        dp[i][0] = dp[i-1][0] + num[i][0];
        dp[0][i] = dp[0][i-1] + num[0][i];
    }
    
    // 动态规划过程
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j];
        }
    }
    
    cout << dp[n-1][n-1] << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        
        // 读入数据
        int[][] num = new int[n][n];
        for(int i = 0; i < n; i++) {
            String[] s = scanner.nextLine().split(",");
            for(int j = 0; j < n; j++) {
                num[i][j] = Integer.parseInt(s[j]);
            }
        }
        
        // 动态规划数组
        int[][] dp = new int[n][n];
        dp[0][0] = num[0][0];
        
        // 初始化第一行和第一列
        for(int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + num[i][0];
            dp[0][i] = dp[0][i-1] + num[0][i];
        }
        
        // 动态规划过程
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + num[i][j];
            }
        }
        
        System.out.println(dp[n-1][n-1]);
    }
}

def main():
    n = int(input())
    
    # 读入数据
    num = []
    for i in range(n):
        row = list(map(int, input().split(',')))
        num.append(row)
    
    # 动态规划数组
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = num[0][0]
    
    # 初始化第一行和第一列
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + num[i][0]
        dp[0][i] = dp[0][i-1] + num[0][i]
    
    # 动态规划过程
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j]
    
    print(dp[n-1][n-1])

if __name__ == "__main__":
    main()