题目链接
// 解法一: 动态规划
// 思路:
// 先根据输入数据构造图
// dfs遍历图,穷举所有可能路径
// 输出路径中的最大值
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
string s;
// 读入数据
void input(vector<vector<int>>& grid) {
int pos = 1;
while(pos < s.size() - 1) {
if(s[pos] == '[') {
vector<int> path;
int num = 0;
pos++;
while(s[pos] != ']') {
num = num * 10 + (int)(s[pos] - 48);
pos++;
if(s[pos] == ',') {
path.push_back(num);
num = 0;
pos++;
}
}
path.push_back(num);
num = 0;
pos++;
grid.push_back(path);
}
pos++;
}
}
void solve() {
vector<vector<int>> grid; // 存储网格图
input(grid);
int n = grid.size();
int m = grid[0].size();
// dp[i][j]的意思是到达grid[i][j]时的路径最大和
vector<vector<int>> dp(n, vector<int>(m, 0));
// 初始化
dp[0][0] = grid[0][0];
for(int i = 1; i < n; ++i) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int i = 1; i < m; ++i) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
// 遍历图,由于每次只能向下或者向右移动一格
// 所以dp[i][j]来自上方或者左侧
// 取两者的最大值 + grid[i][j]就是dp[i][j]的值
for(int i = 1; i < n; ++i) {
for(int j = 1; j < m; ++j) {
dp[i][j] = max(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
}
}
cout << dp[n - 1][m - 1] << endl;
}
int main()
{
while(cin >> s) {
solve();
}
return 0;
}
// 解法二: (因为要找到所有路径,速度比解法一慢很多)
// 思路:
// 先根据输入数据构造图
// dfs遍历图,穷举所有可能路径
// 输出路径中的最大值
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
string s;
int dir[2][2] = {1, 0, 0, 1}; // 存储方向
int ans = 0; // 存储答案
int n, m;
void dfs(vector<vector<int>>& grid, int x, int y, int sum) {
// 如果走到了右下角,取答案最大值
if(x == n - 1 && y == m - 1) {
ans = max(ans, sum);
return;
}
// 遍历两个方向
for(int i = 0; i < 2; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 如果越界则跳过
if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
//回溯
sum += grid[nx][ny];
dfs(grid, nx, ny, sum);
sum -= grid[nx][ny];
}
return;
}
void solve() {
vector<vector<int>> grid; // 存储网格图
int pos = 1;
// 读入数据
while(pos < s.size() - 1) {
if(s[pos] == '[') {
vector<int> path;
int num = 0;
pos++;
while(s[pos] != ']') {
num = num * 10 + (int)(s[pos] - 48);
pos++;
if(s[pos] == ',') {
path.push_back(num);
num = 0;
pos++;
}
}
path.push_back(num);
num = 0;
pos++;
grid.push_back(path);
}
pos++;
}
n = grid.size();
m = grid[0].size();
// dfs找到所有路径中的最大值
dfs(grid, 0, 0, grid[0][0]);
cout << ans << endl;
}
int main()
{
while(cin >> s) {
solve();
}
return 0;
}/**
* 思路：动态规划
* 当解决网格中的路径问题的时候，我们需要考虑如何在每
* 个格子上做出最优的选择，以确保获取最大的路径和。
*
* 对于这个问题，通过创建一个和网格一样大小的二维数组 dp,
* 其中，dp[i][j]代表了从左上角到达格子(i, j)位置的
* 最大路径和。
*
* 其次，对二维数组的第一行和第一列进行初始化，因为
* 这两个方向上只有一种移动方式，即一直向右或一直向下。
* 不受其他方向的影响。
*
* 接下来，从第二行、第二列开始，逐步填充数组 dp，对于
* 位置（i, j)，我们可以从该位置的上方（i - 1, j）和
* 该位置的左方（i, j - 1）移动到当前位置。只需要选择
* 这两个方向中较大的那个路径和，就可到达当前位置的最大路径和。
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String arrayString = scanner.next();
int[][] grid = parse2dArray(arrayString);
System.out.println(maxPathSum(grid));
}
public static int maxPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// 初始化
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 填充数组
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 选择较大的路径和
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
// 将字符串解析为二维数组
public static int[][] parse2dArray(String arrayString) {
String[] rowStrings = arrayString.substring(2, arrayString.length() - 2).split("],");
// "[[1,2,3],[2,3,4],[3,4,5]]" -> "[1,2,3", "[2,3,4", "[3,4,5]"
int rows = rowStrings.length;
int cols = rowStrings[0].split(",").length;
int[][] digital2dArray = new int[rows][cols];
for (int i = 0; i < rows; i++) {
String rowString = rowStrings[i].replaceAll("\\[|\\]", ""); // 去除所有中括号
// "[1,2,3" -> "1,2,3"
// "[2,3,4" -> "2,3,4"
// "[3,4,5]" -> "3,4,5"
String[] elements = rowString.split(",");
// "1,2,3" -> 1 2 3
// "2,3,4" -> 2 3 4
// "3,4,5" -> 3 4 5
for (int j = 0; j < cols; j++) {
digital2dArray[i][j] = Integer.parseInt(elements[j]);
}
}
return digital2dArray;
}
}# 现有一个 m * n的网格，每个网格上都有一个非零整数，每次只能向下或者向右移动一格，计算从左上开始移动到右下的所有路径上数字的最大和。
# 输入：[[2,3,1],[2,5,3],[4,2,1]] 输出：14
# 使用动态规划，与java思路相同
def dp(nums):
m = len(nums)
n = len(nums[0])
if m == 0 or n == 0:
return 0
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = nums[0][0]
for i in range(1, m):
dp[i][0] = nums[i][0] + dp[i-1][0]
for i in range(1, n):
dp[0][i] = nums[0][i] + dp[0][i-1]
for i in range(1, m):
for k in range(1, n):
dp[i][k] = max(dp[i-1][k], dp[i][k-1]) + nums[i][k]
return dp[m-1][n-1]
pass
s = input()
nums = eval(s)
print(dp(nums=nums))