动态规划 | 豁蒙楼

题目

(0908)买卖股票的最佳时机

知识点：数组，动态规划

难度：简单

题目描述：

假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。
示例1
输入 [1,4,2]
输出 3

代码

public static int maxProfit(int[] prices) {
    int buy = Integer.MIN_VALUE;
    int sell = 0;
    for (int i = 0; i < prices.length; i++){
        buy = Math.max(buy, -prices[i]);
        sell = Math.max(sell, prices[i] + buy);
    }
    return sell;
}

(0908)带权值的最小路径和

知识点：数组，动态规划（矩阵）

难度：中等

题目描述：

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。注意：你每次只能向下或向右移动。

public static int minPathSum(int[][] grid) {
    // write code here
    int rows = grid.length;
    int columns = grid[0].length;
    int[][] dp = new int[rows + 1][columns + 1];
    for (int i = 0; i <= rows; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= columns; j++) {
        dp[0][j] = 0;
    }

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (i != 0 && j != 0) {
                dp[i + 1][j + 1] = Math.min(dp[i][j + 1], dp[i + 1][j]) + grid[i][j];
            } else if (i == 0) {
                dp[i + 1][j + 1] = dp[i + 1][j] + grid[i][j];
            } else if (j == 0) {
                dp[i + 1][j + 1] = dp[i][j + 1] + grid[i][j];
            }
        }
    }
    return dp[rows][columns];
}

(0909)子数组的最大累加和

知识点：分治，动态规划
难度：简单
题目描述：
- 给定一个数组arr，返回子数组的最大累加和
- 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
- 要求时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)
理解：问题分为：到某一位为止的最优累加和，和整个数列不同位置为终点的累加和中的最大值(max)。

public int maxsumofSubarray (int[] arr) {
    // write code here
    if (arr.length == 1) return arr[0];
    int currSum = arr[0];
    int maxSum = Integer.MIN_VALUE;
    for (int i = 1; i < arr.length; i++){
        if (currSum <= 0) {
            currSum = arr[i];
        } else {
            currSum += arr[i];
        }
        maxSum = currSum > maxSum ? currSum : maxSum;
    }
    return maxSum;
}

(0911)LIS最长递增子序列（现解法超时）

知识点：二分，动态规划
难度：中等
题目描述：
- 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
目前解法：
- arrayCompare: 先比较长度，再比较字典序
- DP[length]: 逐步更新，长度为length的所有子序列中最优解
- 从arr第一位到最后一位，每次检查以当前位为最后一位的最长递增子序列
- 检查的方法searchInsert：对之前的所有DP[length] (1<=length<=maxlength)遍历，插入当前位arr[i]并舍去大于当前位的部分。这部分用到二分查找。

public class NowCoder_LIS {
    public static int[] LIS(int[] arr) {
        int[][] DP = new int[arr.length][];
        // 括号内表示LIS长度
        DP[0] = new int[] {};
        DP[1] = new int[] { arr[0] };
        int maxlength = 1;
        int[] bestarr = DP[maxlength];

        for (int i = 1; i < arr.length; i++) {
            bestarr = searchInsert(DP[maxlength], arr[i]);
            for (int j = maxlength-1; j >= 1; j--){
                bestarr = arrayCompare(bestarr, searchInsert(DP[j], arr[i]));
            }
            DP[bestarr.length] = bestarr;
            if (bestarr.length > maxlength) maxlength=bestarr.length;
            System.out.printf("arr[%d]: %d, DP[%d] : %s \n", i, arr[i], maxlength, Arrays.toString(DP[maxlength]));
        }
        return DP[maxlength];
    }

    public static int[] arrayCompare(int[] a1, int[] a2) {
        if (a1.length != a2.length) {
            return a1.length > a2.length ? a1 : a2;
        } else {
            // return (Arrays.compare(a1, a2) == 0) ? a1 : a2;
            return (Arrays.toString(a1).compareTo(Arrays.toString(a2)) == 0) ? a1 : a2;
        }
    }

    public static int[] searchInsert(int[] arr, int a) {
        if (arr.length == 0 || a < arr[0]) {
            return new int[] { a };
        } else if (a >= arr[arr.length - 1]) {
            return arrayAppend(arr, a);
        } else {
            int left = 0;
            int right = arr.length - 1;
            while (left + 1 != right){
                int mid = (left + right) >> 1;
                if (arr[mid] > a){
                    right = mid;
                } else {
                    left = mid;
                }
            }
            int[] result = Arrays.copyOfRange(arr, 0, right+1);
            result[result.length - 1] = a;
            return result;
        }
    }

    public static int[] arrayAppend(int[] arr, int a) {
        int[] result = Arrays.copyOf(arr, arr.length + 1);
        result[result.length - 1] = a;
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 9, 13, 12, 11, 1, 2, 8, 6, 4, 15, 14, 7,};
        System.out.println(Arrays.toString(LIS(arr)));
    }
}

(0911)最大正方形

初始化，DP = mat
遍历，包含第[i][j]个结点的最大正方形

状态转移方程:

1
2
3

if mat[i][j] == 1{
    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;
}

import java.util.*;
public class NowCoder_BiggestSquare {
    public static void main(String[] args) {
        char[][] mat = { { '1', '0', '1', '0', '0' }, { '1', '0', '1', '1', '1' }, { '1', '1', '1', '1', '1' },
                { '1', '0', '0', '1', '0' } };
        System.out.println(solve(mat));
    }

    public static int solve(char[][] matrix) {
        // write code here
        if (matrix.length == 0 || matrix[0].length == 0)
            return 0;

        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = matrix[i][j] - '0';
                if (dp[i][j] == 1) {
                    max = 1;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    max = Math.max(dp[i][j], max);
                }
            }
        }
        for (int i = 0; i < m; i++){
            System.out.println(Arrays.toString(dp[i]));
        }
        return max * max;
    }
}

(1117) NC127最长公共子串 LCS

DP[i][j]: 以第i、j个字符为结尾的最长公共子串

import java.util.Arrays;

public class NC127 {
    /**
     * longest common substring
     * 
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public static String LCS(String str1, String str2) {
        // write code here
        int[][] DP = new int[str1.length() + 1][str2.length() + 1];
        int startIdx = 0, endIdx = 0;
        int maxLen = 0;
        String result;

        for (int i = 0; i < str1.length() + 1; i++) {
            DP[i][0] = 0;
        }

        for (int i = 0; i < str2.length() + 1; i++) {
            DP[0][i] = 0;
        }

        for (int i = 1; i < str1.length() + 1; i++) {
            for (int j = 1; j < str2.length() + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    DP[i][j] = DP[i - 1][j - 1] + 1;
                } else {
                    DP[i][j] = Math.min(DP[i - 1][j], DP[i][j - 1]);
                }

                if (DP[i][j] >= maxLen) {
                    maxLen = DP[i][j];
                    endIdx = i;
                }
            }
        }

        startIdx = endIdx - maxLen + 1;

        System.out.printf("startIdx: %d, endIdx: %d \n", startIdx, endIdx);
        for (int i = 0; i < str1.length() + 1; i++) {
            System.out.println(Arrays.toString(DP[i]));
        }

        result = str1.substring(startIdx - 1, endIdx);
        if (result.length() == 0)
            return "-1";

        return result;
    }

    public static void main(String[] args) {
        String str1 = "1AB23456HCDEFG", str2 = "123456QCDEFG";
        System.out.println(LCS(str1, str2));
    }
}

样例结果

startIdx: 10, endIdx: 14 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5]
CDEFG