桌面软件开发跟网站开发那个,免费手机网站模板下载,网站设计主题选择,营销网站建设案例Problem: AcWing 1015. 摘花生 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题。我们需要在一个二维网格中#xff0c;从左上角走到右下角#xff0c;每次只能向右或向下移动#xff0c;目标是使得经过的路径上的数字之和最大。 我们可以定义dp[i][j]为从… Problem: AcWing 1015. 摘花生 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题。我们需要在一个二维网格中从左上角走到右下角每次只能向右或向下移动目标是使得经过的路径上的数字之和最大。 我们可以定义dp[i][j]为从左上角走到(i, j)位置能够得到的最大数字之和。然后我们可以根据dp[i - 1][j]和dp[i][j - 1]来更新dp[i][j]。 解题方法 我们首先初始化dp数组然后从左上角开始遍历每一个位置对于每一个位置我们都有从上面来和从左边来两种情况如果我们从上面来那么dp[i][j] dp[i - 1][j] w[i][j]。如果我们从左边来那么dp[i][j] dp[i][j - 1] w[i][j]。我们取这两种情况的最大值就是dp[i][j]的值。最后dp[r][c]就是我们的答案。 复杂度
时间复杂度: O ( r c ) O(rc) O(rc)因为我们需要遍历每一个位置。 空间复杂度: O ( r c ) O(rc) O(rc)因为我们需要一个二维数组来存储dp值。 Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int t, r, c, m;static int MAXN 110;static int[][] dp new int[MAXN][MAXN];static int[][] w new int[MAXN][MAXN];public static void main(String[] args) throws IOException {t nextInt();while (t-- 0) {r nextInt();c nextInt();for (int i 1; i r; i) {for (int j 1; j c; j) {w[i][j] nextInt();}}for (int i 1; i r; i) {for (int j 1; j c; j) {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]) w[i][j];}}out.println(dp[r][c]);}out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
