AC60. 礼物的最大价值

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] g = {
            {2, 3, 1},
            {1, 7, 1},
            {4, 6, 1}
        };

        int res = getMaxValue(g);
        System.out.println(res);  // 19
    }

    public static int getMaxValue(int[][] g) {
        int n = g.length;
        if (n == 0) return 0;
        int m = g[0].length;

        int[][] f = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++) 
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]) + g[i - 1][j - 1];

        return f[n][m];
    }

}

AC80. 骰子的点数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 1;
        int[] res = numberOfDice(n);
        for (int i = n; i < res.length; i ++) {
            System.out.print(res[i]);  // 1 1 1 1 1 1    
            System.out.print(" ");
        }

    }

    public static int[] numberOfDice(int n) {
        int[][] f = new int[n + 1][n * 6 + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i * 6; j ++)
                for (int k = 1; k <= Math.min(6, j); k ++)
                    f[i][j] += f[i - 1][j - k];

        int[] res = new int[n * 6 + 1];
        for (int i = n; i <= n * 6; i ++) res[i] = f[n][i];
        return res;
    }

}

AC83. 股票的最大利润

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {9, 11, 8, 5, 7, 12, 16, 14};
        int res = maxDiff(nums);

        System.out.println(res);  // 11
    }

    public static int maxDiff(int[] nums) {
        if (nums.length == 0) return 0;
        int res = 0;
        for (int i = 1, minv = nums[0]; i < nums.length; i ++) {
            res = Math.max(res, nums[i] - minv);
            minv = Math.min(minv, nums[i]);
        }

        return res;
    }

}

LC10. 正则表达式匹配

import java.util.*;

public class Main {
    public static void main (String[] args) { 

        String s = "aa", p = "a";

        boolean res = isMatch(s, p);
        System.out.println(res);  // false

        /* 
        String s = "aa", p = "a*";

        boolean res = isMatch(s, p);
        System.out.println(res);  // true
        */
    }

    public static boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        s = " " + s; p = " " + p;
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i <= n; i ++)
            for (int j = 1; j <= m; j ++) {
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') continue;
                if (i != 0 && p.charAt(j) != '*') 
                    f[i][j] = f[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                else if (p.charAt(j) == '*') f[i][j] = f[i][j - 2] || 
                        i != 0 && f[i - 1][j] &&
                        (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
            }
        return f[n][m];
    }

}

LC45. 跳跃游戏 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 3, 1, 1, 4};

        int res = jump(nums);
        System.out.println(res);  // 2
    }

    public static int jump(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];

        for (int i = 1, j = 0; i < n; i ++) {
            while (j + nums[j] < i) j ++;
            f[i] = f[j] + 1;
        }

        return f[n - 1];
    }

}

LC55. 跳跃游戏

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 3, 1, 1, 4}; // true
        // int[] nums = {3, 2, 1, 0, 4}; // false

        boolean res = canJump(nums);
        System.out.println(res);  
    }

    public static boolean canJump(int[] nums) {
        for (int i = 0, j = 0; i < nums.length; i ++) {
            if (j < i) return false;
            j = Math.max(j, i + nums[i]);
        }

        return true;
    }

}

LC62. 不同路径

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        // int m = 3, n = 7; // 28
        int m = 3, n = 2; // 3

        int res = uniquePaths(m, n);
        System.out.println(res);  
    }

    public static int uniquePaths(int m, int n) {
        int[][] f = new int[n][m];
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++) 
                if (i == 0 && j == 0) f[i][j] = 1;
                else {
                    if (i != 0) f[i][j] += f[i - 1][j];
                    if (j != 0) f[i][j] += f[i][j - 1];
                }
        return f[n - 1][m - 1];
    }

}

LC63. 不同路径 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] matrix = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };

        int res = uniquePathsWithObstacles(matrix);
        System.out.println(res);   // 2
    }

    public static int uniquePathsWithObstacles(int[][] matrix) {
        int n =matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;

        int[][] f = new int[n][m];
        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < m; j ++)
                if (matrix[i][j] == 0) {
                    if (i == 0 && j == 0) f[i][j] = 1;
                    else {
                        if (i != 0) f[i][j] += f[i - 1][j];
                        if (j != 0) f[i][j] += f[i][j - 1];
                    }
                }
        return f[n - 1][m -1];
    }

}

LC64. 最小路径和

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] g = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        }; // 7

        /*
        int[][] g = {
            {1, 2, 3},
            {4, 5, 6}
        }; // 12
        */
        int res = minPathSum(g);
        System.out.println(res);   
    }

    public static int minPathSum(int[][] g) {
        int n = g.length;
        if (n == 0) return 0;
        int m = g[0].length;

        int[][] f = new int[n][m];
        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < m; j ++)
                f[i][j] = Integer.MAX_VALUE;

        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < m; j ++) {
                if (i == 0 && j == 0) f[i][j] = g[i][j];
                else {
                    if (i != 0) f[i][j] = Math.min(f[i][j], f[i - 1][j] + g[i][j]);
                    if (j != 0) f[i][j] = Math.min(f[i][j], f[i][j - 1] + g[i][j]);
                }
            }

        return f[n - 1][m -1];
    }

}

LC72. 编辑距离

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        String a = "horse", b = "ros"; // 3
        // String a = "intention", b = "execution"; // 5
        int res = minDistance(a, b);

        System.out.println(res);   
    }

    public static int minDistance(String a, String b) {
        int n = a.length(), m = b.length();
        a = " " + a;
        b = " " + b;

        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i ++) f[i][0] = i;
        for (int i = 1; i <= m; i ++) f[0][i] = i;

        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1;
                int t;
                if (a.charAt(i) != b.charAt(j)) t = 1;
                else t = 0;

                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + t);
            }

        return f[n][m];
    }

}

LC97. 交错字符串

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        String a = "aabcc", b = "dbbca", c = "aadbbcbcac";  // true
        // String a = "aabcc", b = "dbbca", c = "aadbbbaccc";  // false
        boolean res = isInterLeave(a, b, c);

        System.out.println(res);   
    }

    public static boolean isInterLeave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if (s3.length() != n + m) return false;
        boolean[][] f = new boolean[n + 1][m + 1];

        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        for (int i = 0; i <= n; i ++) 
            for (int j = 0; j <= m; j ++) 
                if (i == 0 && j == 0) f[i][j] = true;
                else {
                    if (i != 0 && s1.charAt(i) == s3.charAt(i + j)) f[i][j] = f[i - 1][j];
                    if (j != 0 && s2.charAt(j) == s3.charAt(i + j)) f[i][j] = f[i][j] || f[i][j - 1];
                }

        return f[n][m];
    }

}

LC120. 三角形最小路径和

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> tri1 = new ArrayList<>();
        tri1.add(2);

        List<Integer> tri2 = new ArrayList<>();
        tri2.add(3);
        tri2.add(4);

        List<Integer> tri3 = new ArrayList<>();
        tri3.add(6);
        tri3.add(5);
        tri3.add(7);

        List<Integer> tri4 = new ArrayList<>();
        tri4.add(4);
        tri4.add(1);
        tri4.add(8);
        tri4.add(3);

        triangle.add(tri1);
        triangle.add(tri2);
        triangle.add(tri3);
        triangle.add(tri4);

        int res = minimumTotal(triangle);

        System.out.println(res);   
    }

    public static int minimumTotal(List<List<Integer>> f) {
        for (int i = f.size() - 2; i >= 0; i --) 
            for (int j = 0; j <= i; j ++)
                f.get(i).set(j, f.get(i).get(j) + 
                Math.min(f.get(i + 1).get(j), f.get(i + 1).get(j + 1)));

        return f.get(0).get(0);
    }

}

LC121. 买卖股票的最佳时机

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] prices = {7, 1, 5, 3, 6, 4};
        int res = maxProfit(prices);

        System.out.println(res);  // 5
    }

    public static int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 0, minp = Integer.MAX_VALUE; i < prices.length; i ++) {
            res = Math.max(res, prices[i] - minp);
            minp = Math.min(minp, prices[i]);
        }

        return res;
    }

}

LC122. 买卖股票的最佳时机 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] prices = {7, 1, 5, 3, 6, 4};
        int res = maxProfit(prices);

        System.out.println(res);  // 7
    }

    public static int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 0; i + 1 < prices.length; i ++)
            res += Math.max(0, prices[i + 1] - prices[i]);

        return res;
    }

}

LC123. 买卖股票的最佳时机 III

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
        int res = maxProfit(prices);

        System.out.println(res);  // 6
    }

    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int[] f = new int[n + 2];
        for (int i = 1, minp = Integer.MAX_VALUE; i <= n; i ++) {
            f[i] = Math.max(f[i - 1], prices[i - 1] - minp);
            minp = Math.min(minp, prices[i - 1]);
        }

        int res = 0;
        for (int i = n, maxp = 0; i != 0; i --) {
            res = Math.max(res, maxp - prices[i - 1] + f[i - 1]);
            maxp = Math.max(maxp, prices[i - 1]);
        }

        return res;
    }

}

LC132. 分割回文串 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        String s = "aab"; // 1
        // String s = "a"; // 0;
        // String s = "ab"; // 1
        int res = minCut(s);

        System.out.println(res);  // 
    }

    public static int minCut(String s) {
        int n = s.length();
        s = " " + s;
        boolean[][] g = new boolean[n + 1][n + 1];

        int[] f = new int[n + 1];
        for (int i = 0; i < n + 1; i ++) f[i] = 0x3f3f3f3f;

        for (int j = 1; j <= n; j ++)
            for (int i = 1; i <= n; i ++)
                if (i == j) g[i][j] = true;
                else if (s.charAt(i) == s.charAt(j)) 
                    if (i + 1 > j - 1 || g[i + 1][j + 1] == true) g[i][j] = true;

        f[0] = 0;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i; j ++)
                if (g[j][i] == true)
                    f[i] = Math.min(f[i], f[j - 1] + 1);
        return f[n] - 1;
    }

}

LC134. 加油站

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2}; // 3

        // int[] gas = {2, 3, 4};
        // int[] cost = {3, 4, 3}; // -1

        int res = canCompleteCircuit(gas, cost);

        System.out.println(res);  
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0, j; i < n; ) {
            int left = 0;
            for (j = 0; j < n; j ++) {
                int k = (i + j) % n;
                left += gas[k] - cost[k];
                if (left < 0) break;
            }

            if (j == n) return i;
            i = i + j + 1;
        }        
        return -1;
    }

}

LC135. 分发糖果

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] ratings = {1, 0, 2}; // 5
        // int[] ratings = {1, 2, 2}; // 4
        int res = candy(ratings);

        System.out.println(res);  
    }

    public static int[] f;
    public static int[] w;
    public static int n;

    public static int dp(int x) {
        if (f[x] != -1) return f[x];
        f[x] = 1;
        if (x != 0 && w[x - 1] < w[x]) f[x] = Math.max(f[x], dp(x - 1) + 1);
        if (x + 1 < n && w[x + 1] < w[x]) f[x] = Math.max(f[x], dp(x + 1) + 1);
        return f[x];
    }

    public static int candy(int[] ratings) {
        n = ratings.length;
        w = ratings;
        f = new int[n];
        for (int i = 0; i < n; i ++) f[i] = -1;
        int res = 0;
        for (int i = 0; i < n; i ++) res += dp(i);
        return res;
    }

}

LC152. 乘积最大子数组

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 3, -2, 4}; // 6
        // int[] nums = {-2, 0, -1}; // 0

        int res = maxProduct(nums);

        System.out.println(res);  
    }

    public static int maxProduct(int[] nums) {
         int res = nums[0];
         int f = nums[0], g = nums[0];
         for (int i = 1; i < nums.length; i ++) {
             int a = nums[i], fa = f * a, ga = g * a;
             f = Math.max(a, Math.max(fa, ga));
             g = Math.min(a, Math.min(fa, ga));
             res = Math.max(res, f);
         }

         return res;
    }

}

LC174. 地下城游戏

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] w = {
            {-2, -3, 3},
            {-5, -10, 1},
            {10, 30, -5}
        };

        int res = calculateMinimumHP(w);

        System.out.println(res);  // 7
    }

    public static int calculateMinimumHP(int[][] w) {
        int n = w.length;
        int m = w[0].length;
        int[][] f = new int[n + 10][m + 10];

        for (int i = n - 1; i >= 0; i --) 
            for (int j = m - 1; j >= 0; j --) {
                f[i][j] = 0x3f3f3f3f;
                if (i == n - 1 && j == m - 1) f[i][j] = Math.max(1, 1 - w[i][j]);
                else {
                    if (i + 1 < n) f[i][j] = f[i + 1][j] - w[i][j];
                    if (j + 1 < n) f[i][j] = Math.min(f[i][j], f[i][j + 1] - w[i][j]);
                    f[i][j] = Math.max(1, f[i][j]);
                }
            }
        return f[0][0];

    }

}

LC 198. 打家劫舍

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3, 1}; // 4
        // int[] nums = {2, 7, 9, 3, 1}; // 12

        int res = rob(nums);

        System.out.println(res); 
    }

    public static int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];

        for (int i = 0; i < n + 1; i ++) f[i] = -0x3f3f3f3f;
        f[0] = 0;

        for (int i = 1; i <= n; i ++) {
            int w = nums[i - 1];
            if (i == 1) f[i] = w;
            else if (i == 2) f[i] = Math.max(f[i - 1], w);
            else f[i] = Math.max(f[i - 1], f[i - 2] + w);
        }

        return f[n];
    }

}

LC213. 打家劫舍 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 3, 2}; // 3
        // int[] nums = {1, 2, 3, 1}; // 4

        int res = rob(nums);

        System.out.println(res); 
    }

    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        for (int i = 2; i <= n; i ++) {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = Math.max(f[i - 1], g[i -  1]);
        }

        int res = Math.max(f[n], g[n]);
        f[1] = nums[0];
        g[1] = Integer.MIN_VALUE;

        for (int i = 2; i <= n; i ++) {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        return Math.max(res, g[n]);
    }

}

LC221. 最大正方形

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        char[][] matrix = {
            {'1','0','1','0','0'},
            {'1','0','1','1','1'}, 
            {'1','1','1','1','1'}, 
            {'1','0','0','1','0'}
        }; 

        int res = maximalSquare(matrix);
        System.out.println(res);  // 4
    }

    public static int maximalSquare(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int n = matrix.length, m = matrix[0].length;
        int[][] f = new int[n + 1][m + 1];
        int res = 0;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                if (matrix[i - 1][j - 1] == '1') {
                    f[i][j] = Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;
                    res = Math.max(res, f[i][j]);
                }
        return res * res;
    }

}