题目简介

一个矩阵花生，每个交错点都有花生，数量靠用户输入，从左上出发到右下，怎么样走踩到的花生最多

DP问题思考方式

状态表示 F [ i，j ]

含义：所有从（1，1） 走到（i，j）的路线的集合
属性：Max/Min/数量

状态计算

集合划分：
主要按照最后一种情况来划分，且保留最后一个
1.从上下来到终点
2.从左边往右走到终点

举个例子（状态表示）

f（2，3）需要注意在算法中行列的一种概念模型。
含义：如图表示所有2行3列的所有路线的最大值
image.png
image.png

举个例子（状态计算）

是从最后一步来划分
一种情况是从上下来到终点
另一种是从左边往右走到终点
f[i-1，j] + w[i，j] 红色箭头
f[i , j-1] + w[i , j] 绿色箭头

image.png
image.png
代码

  1. package lanqiaobei.dp;
  2. import java.util.Scanner;
  3. public class peanut {
  4.     /*花生数*/
  5.     static int[][] w = new int[110][110];
  6.     static int[][] f = new int[110][110];
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         int count = sc.nextInt();
  10.         while((count--)>0){
  11.             int row = sc.nextInt();
  12.             int column = sc.nextInt();
  13.             /*外部输入值*/
  14.             for (int i = 1; i <= row; i++) {
  15.                 for (int j = 1; j <= column; j++) {
  16.                     w[i][j] = sc.nextInt();
  17.                 }
  18.             }
  19.             /*计算最小*/
  20.             for (int i = 1; i <= row; i++) {
  21.                 for (int j = 1; j <= column; j++) {
  22.                     f[i][j] = Math.max(f[i-1][j]+w[i][j],f[i][j-1]+w[i][j]);
  23.                 }
  24.             }
  25.             System.out.println(f[row][column]);
  26.         }
  27.     }
  29. }