問(wèn)題描述

???????Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0) by following these certain set of rules :

1.From a cell (i, j) we can move to (i+1, j) or (i, j+1).
2.We cannot move from (i, j) if your overall points at (i, j) is <= 0.
3.We have to reach at (n-1, m-1) with minimum positive points i.e., > 0.

輸入

???????The first line contains an integer 'T' denoting the total number of test cases.In each test cases, the first line contains two integer 'R' and 'C' denoting the number of rows and column of array.
The second line contains the value of the array i.e the grid, in a single line separated by spaces in row major order.

Constraints:
1 ≤ T ≤ 30
1 ≤ R,C ≤ 10
-30 ≤ A[R][C] ≤ 30

1
3 3
-2 -3 3 -5 -10 1 10 30 -5

輸出

???????Print the minimum initial points to reach the bottom right most cell in a separate line.

7

解釋:
???????7 is the minimum value to reach destination with positive throughout the path. Below is the path.

???????(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)

???????We start from (0, 0) with 7, we reach(0, 1) with 5, (0, 2) with 2, (1, 2) with 5, (2, 2)with and finally we have 1 point (we needed greater than 0 points at the end).

思路

???????動(dòng)態(tài)規(guī)劃問(wèn)題，構(gòu)建矩陣dp[i][j]表示從輸入矩陣的（i,j）位置走到右下角的最小初始值，根據(jù)不同的情況填充之：

1.最后一步

???????如果最后一格的值大于0，則只需要初始值為1就可走過(guò)它；如果小于0，則需要比其絕對(duì)值大1的初始值才能走過(guò)它：

2.最后一列

???????，因?yàn)橹荒芟蛳伦?，所以結(jié)果為該列下一行所需的初始值加上本次的消耗（正消耗是負(fù)數(shù)，所以用減），但最終結(jié)果不能小于1：

3.最后一行

???????因?yàn)橹荒芟蛴易?，所以結(jié)果為該行下一列所需的初始值加上本次的消耗（正消耗是負(fù)數(shù)，所以用減），但最終結(jié)果不能小于1：

4.其他位置

???????在其他位置上既可向下走，也可向右走，選擇二者dp值更小的那邊，減去本次的消耗，最終結(jié)果同樣不能小于1：

代碼

import java.util.Scanner;

public class Main{
    static int minInitialPoints(int points[][],int R,int C)
    {
        int dp[][] = new int[R][C];
        int m = R, n = C;

        // 最后一步
        dp[m-1][n-1] = points[m-1][n-1] > 0? 1:
                Math.abs(points[m-1][n-1]) + 1;

        // 最后一行與最后一列
        for (int i = m-2; i >= 0; i--)
            dp[i][n-1] = Math.max(dp[i+1][n-1] - points[i][n-1], 1);
        for (int j = n-2; j >= 0; j--)
            dp[m-1][j] = Math.max(dp[m-1][j+1] - points[m-1][j], 1);

        // 其他地方
        for (int i=m-2; i>=0; i--)
        {
            for (int j=n-2; j>=0; j--)
            {
                int min_points_on_exit = Math.min(dp[i+1][j], dp[i][j+1]);
                dp[i][j] = Math.max(min_points_on_exit - points[i][j], 1);
            }
        }
        return dp[0][0];
    }

    public static void main (String args[])
    {
        Scanner sc = new Scanner(System.in);
        int case_num = sc.nextInt();
        sc.nextLine();
        while(case_num>0) {
            String[] temp = sc.nextLine().split(" ");
            int rows = Integer.parseInt(temp[0]);
            int cols = Integer.parseInt(temp[1]);
            int[][] inputs = new int[rows][cols];
            String[] temp2 = sc.nextLine().split(" ");
            for (int i=0;i<temp2.length;i++){
                inputs[i/cols][i%cols] = Integer.parseInt(temp2[i]);
            }
            System.out.println(minInitialPoints(inputs,rows,cols));
            case_num --;
        }
        sc.close();
    }
}