算法：动态规划 - zhpanvip/AndroidNote GitHub Wiki

5. 最长回文子串

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }
    int maxLen = 1;
    int begin = 0;
    boolean[][] dp = new boolean[len][len];
    for (int i = 0; i < len; i++) {
        // 长度为1的字串一定是回文串
        dp[i][i] = true;
    }
    char[] chars = s.toCharArray();
    // l表示枚举字符串长度,长度应该小于等于s的长度
    for (int l = 2; l <= len; l++) {
        // i表示子串的起点，i表示坐标，所以只能小于s的长度
        for (int i = 0; i < len; i++) {
            // j 表示字串的终点
            int j = i + l - 1;
            // 超过字符串的长度，重新开始
            if (j >= len) {
                break;
            }
            // 只有起点和终点相等，i到j的这个字串才有可能是回文串
            if (chars[i] == chars[j]) {
                if (j - i <= 2) {
                    // 当字串长度为2或者3时，起点和终点相等，那么一定是回文串
                    dp[i][j] = true;
                } else {
                    // 当字串长度大于3时，除了起点与终点相等之外，中间的字串必须也要满足是回文串
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    return s.substring(begin, begin + maxLen);
}

70. 爬楼梯

• 解法一：动态规划

public int climbStairs2(int n) {
    int[] dp = new int[n + 1];
    // 0阶有1种走法
    dp[0] = 1;
    // 1阶1种走法
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        // 到达第i阶可能是一步到达，也可能是两步到达，因此到第i阶的走法应该是i-1和i-2的总和。
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

• 解法二：递归

public int climbStairs1(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (map.containsKey(n)) {
        return map.get(n);
    }
    int sum = climbStairs1(n - 1) + climbStairs1(n - 2);
    map.put(n, sum);
    return sum;
}

121. 买卖股票的最佳时机

• 解法一：动态规划

public int maxProfit(int[] prices) {
    int len = prices.length;
    // 特殊判断
    if (len < 2) {
        return 0;
    }
    int[][] dp = new int[len][2];

    // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
    // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数

    // 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 从第 2 天开始遍历
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    }
    return dp[len - 1][0];
}

• 解法二：暴力法

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

• 解法三：一次循环

public int maxProfit1(int[] prices) {
    if(prices.length == 0){
        return 0;
    }
    int minPrice = prices[0], maxProfile = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfile = Math.max(maxProfile,prices[i] - minPrice);
        }
    }
    return maxProfile;
}