侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【动态规划】摘花生「动态规划之数字三角形模型」

GabrielxD
2023-02-09 / 0 评论 / 0 点赞 / 69 阅读 / 656 字
温馨提示:
本文最后更新于 2023-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1015. 摘花生 - AcWing题库


Hello Kitty 想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。

地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走,不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

1.gif

输入格式

第一行是一个整数T,代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1T1001 \le T \le 100 ,
1R,C1001 \le R,C \le 100 ,
0M10000 \le M \le 1000

输入样例:

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例:

8
16

解题

方法一:动态规划 数字三角形模型

思路

动态规划:

  • 状态定义:dp[i][j]dp[i][j] 表示所有从 (1,1)(1, 1) 开始走到 (i,j)(i, j) 的路径上数字和的最大值
  • 状态转移方程:dp[i][j]=max(dp[i1][j]+g[i][j],dp[i][j1]+g[i][j])dp[i][j] = \max(dp[i-1][j] + g[i][j], dp[i][j - 1] + g[i][j])
  • 初始状态:dp[1][1]=g[1][1]dp[1][1] = g[1][1]

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 110;
    static int t, r, c;
    static int[][] dp = new int[N][N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            r = (int) in.nval;
            in.nextToken();
            c = (int) in.nval;
            for (int i = 1; i <= r; ++i) {
                for (int j = 1; j <= c; ++j) {
                    in.nextToken();
                    int m = (int) in.nval;
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + m;
                }
            }
            System.out.println(dp[r][c]);
        }
    }
}
0

评论区