174. Dungeon Game

这题tag既是DP也是binary search，但我没放在binary search，因为DP的话只要O(mn)，而binary search得O(mn logn)。

先讲DP方法。建立一个二维数组来放到达P格所需的生命值，health[ i ][ j ]就表示从i，j位置的格子出发到P格所需的生命值，我们的目标就是求得health[ 0 ][ 0 ]。

我们可以从P格入手。当K到达了P格，只要保证P格的生命值大于等于1就行，因此我们有health[ i ][ j ]=Math.max(1, 1-dungeon[ i ][ j ])

如果P格为正数，那无所谓只要到达前生命值大于等于1就行，如果P格为负数，我们就要额外的生命值再到达P格。然后有了最重要的这一步Math.max(1, 1-dungeon[i][j])，后面的就好做了。

对于最下面一排和最右边一排，因为只能一个方向走，就很好判断。以最右边为例，只能往下走，因此health[ i ][ j ]=Math.max(1, health[ i+1 ][ j ]-dungeon[ i ][ j ])。这里i，j位置的最小所需生命值取决于下面的格子的所需生命值减去i，j位置要扣去的生命值。

对于其他位置的格子，因为要optimal路线，所以我们会选所需生命值最小的格子作为下一个移动的格子，比如我往右的格子所需生命值为5，往下的格子所需生命值为4，那当然往下走，因为往下走的话我只需要更小的生命值就能到达P位置。因此有health[ i ][ j ]=Math.max(1, Math.min(health[ i+1 ][ j ], health[ i ][ j+1 ])-dungeon[ i ][ j ])。

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length;
        int n=dungeon[0].length;
        int[][] res=new int[m][n];
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(i==m-1&&j==n-1){
                    res[i][j]=Math.max(1, 1-dungeon[i][j]);
                }
                else if(i==m-1){
                        res[i][j]=Math.max(1, res[i][j+1]-dungeon[i][j]);
                }
                else if(j==n-1){
                        res[i][j]=Math.max(1, res[i+1][j]-dungeon[i][j]);
                }
                else {
                    res[i][j]=Math.max(1, Math.min(res[i+1][j], res[i][j+1])-dungeon[i][j]);
                }
            }
        }
        return res[0][0];
    }
}

121. Best Time to Buy and Sell Stock

逻辑比较简单。如果一直递减数列，那肯定没戏。碰到不递减的元素开始，记录前面的值，因为前面的值为最小值，在不递减的前提下，一直更新差值，直到出现更小的，更新最小值，对于不递减的元素，继续更新差值。

public class Solution {
    public int maxProfit(int[] prices) {
        int min=Integer.MAX_VALUE;
        int res=0;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min)
                min=prices[i];
            else {
                res=Math.max(prices[i]-min, res);
            }
        }
        return res;
    }
}

120. Triangle

三角形相当于树状结构，每个父元素对应2个子元素。

对于第i行第j列元素，它的最小路径和取决于它的两个子元素的最小值。因此我们只需用一个数组来存当前行的所有元素最小路径和就行了。

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] res=new int[triangle.size()+1];
        for(int i=triangle.size()-1;i>=0;i--){
            List<Integer> sub=triangle.get(i);
            for(int j=0;j<sub.size();j++){
                res[j]=Math.min(res[j], res[j+1])+sub.get(j);
            }
        }
        return res[0];
    }
}