最小化初始点（动态规划）

问题描述

       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).

思路

       动态规划问题，构建矩阵dp[i][j]表示从输入矩阵的（i,j）位置走到右下角的最小初始值，根据不同的情况填充之：

1.最后一步

       如果最后一格的值大于0，则只需要初始值为1就可走过它；如果小于0，则需要比其绝对值大1的初始值才能走过它：

2.最后一列

       ，因为只能向下走，所以结果为该列下一行所需的初始值加上本次的消耗（正消耗是负数，所以用减），但最终结果不能小于1：

3.最后一行

       因为只能向右走，所以结果为该行下一列所需的初始值加上本次的消耗（正消耗是负数，所以用减），但最终结果不能小于1：

4.其他位置

       在其他位置上既可向下走，也可向右走，选择二者dp值更小的那边，减去本次的消耗，最终结果同样不能小于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();
    }
}