代码分析

典型的动态规划，走的顺序就是从下到上从右到左，举出几个例子，就可以确定状态转移方程

代码实现

int[][] dp=new int[dungeon.length][dungeon[0].length];
        //init
        //dp[dungeon.length-1][dungeon[0].length-1]=dungeon[dungeon.length-1][dungeon[0].length-1]>=0?1:dungeon[dungeon.length-1][dungeon[0].length-1]*-1+1;
        for(int i=dungeon.length-1;i>-1;i--)
        {
            for(int j=dungeon[0].length-1;j>-1;j--)
            {
                if(i==dungeon.length-1&&j==dungeon[0].length-1)//如果是最后一个元素
                {
                    dp[i][j]=dungeon[i][j]>=0?1:dungeon[i][j]*-1+1;
                }else if(i==dungeon.length-1)//如果是最后一行
                {
                    if(dp[i][j+1]==1&&dungeon[i][j]>0)
                    {
                        dp[i][j]=1;
                    }else if(dp[i][j+1]!=1&&dungeon[i][j]>=dp[i][j+1])
                    {
                        dp[i][j]=1;
                    }else
                    {
                        dp[i][j]=dp[i][j+1]-dungeon[i][j];
                    }
                }else if(j==dungeon[0].length-1)
                {
                    if(dp[i+1][j]==1&&dungeon[i][j]>0)
                    {
                        dp[i][j]=1;
                    }else if(dp[i+1][j]!=1&&dungeon[i][j]>=dp[i+1][j])
                    {
                        dp[i][j]=1;
                    }else
                    {
                        dp[i][j]=dp[i+1][j]-dungeon[i][j];
                    }
                }else
                {
                    int min=Math.min(dp[i+1][j],dp[i][j+1]);
                    //System.out.println(min);
                    if(min==1&&dungeon[i][j]>0)
                    {
                        dp[i][j]=1;
                    }else if(min!=1&&dungeon[i][j]>=min)
                    {
                        dp[i][j]=1;
                    }else
                    {
                        dp[i][j]=min-dungeon[i][j];
                    }
                }
            }
        }
        return dp[0][0];

优化的解法

 public static int calculateMinimumHP(int[][] dungeon) {
        int[][] dp=new int[dungeon.length][dungeon[0].length];
        for(int i=dungeon.length-1;i>-1;i--)
        {
            for(int j=dungeon[0].length-1;j>-1;j--)
            {
                if(i==dungeon.length-1&&j==dungeon[0].length-1)//如果是最后一个元素
                {
                    dp[i][j]=dungeon[i][j]>=0?1:dungeon[i][j]*-1+1;
                }else if(i==dungeon.length-1)//如果是最后一行
                {
                    dp[i][j]=Math.max(1,dp[i][j+1]-dungeon[i][j]);
                }else if(j==dungeon[0].length-1)
                {
                    dp[i][j]=Math.max(1,dp[i+1][j]-dungeon[i][j]);
                }else
                {
                    int min=Math.min(dp[i+1][j],dp[i][j+1]);
                    dp[i][j]=Math.max(1,min-dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }