动态规划

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = 1;
    int maxans = 1;
    for (int i = 1; i < nums.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxans = Math.max(maxans, dp[i]);
    }
    return maxans;
}

    //amount=11,可以从dp[10],dp[9],dp[6]3个地方到达
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        //(1)初始化DP table，零钱为0则硬币0个
        int[] dp = new int[amount + 1];
        dp[0] = 0;

        //(2)遍历每种【状态】即金额，【选择】即保存最少硬币数量
        for (int amounttt = 1; amounttt <= amount; amounttt++) {
            //(1.1)初始化DP table。初始为最大硬币数量即amount个，因为最小面额为1元，那么+1即为无法到达的硬币个数。当然取(amount+1,Integer.MAX_VALUE - 1)(ps:后面存在1+dp[balance]计算)范围都可
            dp[amounttt] = amount + 1;
            //(3)遍历每种面额的硬币
            for (int coin : coins) {
                //(3.1)剩余金额balance，为当前amount-某额度硬币
                int balance = amounttt - coin;
                //(3.2)剩余额度>=0，说明该种硬币的组合可行
                if (balance >= 0) {
                    //(3.3)说明amount额度足以减去某额度硬币。balance<amounttt，balance于前面已经计算保存好【状态】，+1为加上当前硬币
                    //例如1：coins[1,2,5]，amounttt=4
                    //①balance=4-1，此时dp[4]=min(初始值,1+dp[3]）,而dp[3]由1元+2元组合为2枚。保存最小值dp[4]=3
                    //②balance=4-2，此时dp[4]=min(初始值,1+dp[2])，而dp[2]由2元组合为1枚。保存最小值dp[4]=2
                    //③balance=4-5，不足以减去该面额
                    //例如2:coins[3]，amounttt=5。dp则为[0,max,max,1,max,max,max]，毕竟max<max+1
                    dp[amounttt] = Math.min(dp[amounttt], 1 + dp[balance]);
                }
            }
        }

        //(4)如amount等于初始值，说明在给定种类的硬币中无法组合成amount元。比如coin[2,3] amount=1,4...
        return dp[amount] == (amount + 1) ? -1 : dp[amount];
    }

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    //初始化为+1是为了当dp[0][0]时可以表示的为空字符串和另外一个字符串的匹配
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        char c1 = text1.charAt(i - 1);
        for (int j = 1; j <= n; j++) {
            char c2 = text2.charAt(j - 1);
            if (c1 == c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}

    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }