2022-11-02 00:05 已编辑华东师范大学 iOS开发发布于上海

关注

刷题记录｜目标101题--动态规划

写在前面

开个贴记录一下刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

贪心算法：https://www.nowcoder.com/discuss/1051877
双指针：https://www.nowcoder.com/discuss/1057237
二分查找：https://www.nowcoder.com/discuss/1059986
排序：链接
搜索：链接

动态规划

一维动态规划

No.1 Climbing Stairs

链接

解题思路：

dp[i] = dp[i-1] + dp[i-2]

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n];
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; i ++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

No.2 House Robber

链接

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i ++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

No.3 Arithmetic Slices

题目：链接

解题思路：

本题需要注意两点：

成为一个Arithmetic Slices 的条件可以抽象为nums[i] - nums[i-1] == nums[i-1] - nums[i-2]
每个位置一共有多少种可能性很难用dp计算出，但是我们可以dp出以nums[i]结尾的Arithmetic Slices数量为 dp[i] = dp[i-] + 1，因为当nums[i] - nums[i-1] == nums[i-1] - nums[i-2]时，每个以i-1结尾的Arithmetic Slices都可以加上 nums[i]构成Arithmetic Slices，同时还有一个nums[i-2],num[i-1],nums[i]的组合，所以一共会比以i-1结尾的dp多一，最后求和即可。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;
        int[] dp = new int[n];
        int result = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                result += dp[i];
            }
        }
        return result;
    }
}

No.4 House Robber II

题目：链接

解题思路：

这里的问题是nums首尾相连了，所以为了防止成环，我们选用从第1个开始开始偷到n-1个和从第2个开始偷到第n个，分别取最大值，最后两者比较

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0],nums[1]);
        return Math.max(dpSolution(nums,0,n - 2,n),dpSolution(nums,1,n - 1,n));
    }
    private int dpSolution(int[] nums, int l ,int r, int n) {
        int[] dp = new int[n];
        dp[l] = nums[l];
        dp[l + 1] = Math.max(nums[l], nums[l + 1]);
        for (int i = l + 2; i <= r; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[r];
    }
}

No.5 Maximum Subarray

题目：链接

解题思路：

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int dp = nums[0];
        int sum = dp;
        for (int i = 1; i < n; i++) {
            dp = Math.max(dp + nums[i],nums[i]);
            sum = Math.max(sum, dp);
        }
        return sum;
    }
}

二维动态规划

No.1 Minimum Path Sum

题目：链接

解题思路：

位置i,j的值等于其上和左的两个dp取较小值加上他自己的取值，既dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j],dp[i][j -1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}

No.2 01 Matrix

题目：链接

解题思路：

本题的dp[i][j]其实等于上下左右四个方位的最小值+1，但是由于我们顺序遍历的时候无法获取下和右的值，所有我们先从左到右从上到下遍历一遍赋值，再从右到左从下到上反着走一遍取最小值

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 && j == 0) {
                        dp[0][0] = 100000;
                    } else if (j == 0) {
                        dp[i][j] = dp[i - 1][j] + 1;
                    } else if (i == 0) {
                        dp[i][j] = dp[i][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.min(dp[i][j - 1],dp[i - 1][j]) + 1;
                    }
                }
            }
        }
        for (int i = m -1; i >= 0; i--) {
            for (int j = n -1; j >= 0; j--) {
                if (mat[i][j] == 1) {
                    if (i == m -1 && j == n -1) {
                        continue;
                    } else if (i == m - 1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                    } else if (j == n - 1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                    } else {
                        dp[i][j] = Math.min(dp[i][j],Math.min(dp[i][j + 1],dp[i + 1][j]) + 1);
                    }
                }
            }
        }
        return dp;
    }
}

No.3 Maximal Square

题目：链接

解题思路：

这样的求正方形的题需要一个二维dp数组，但是怎么求dp[i][j]的值呢？

如果nums[i][j] == 0,则 dp[i][j] = 0,

如果nums[i][j]==1

我们假设dp[i][j] = k²,则他的上元素，左元素和上左元素都需要不小于 (k - 1)²,
nums[i-1][j] >= (k - 1)²&& nums[i][j-1] >= (k - 1)² && nums[i-1][j-1] >= (k - 1)²，即下图所示

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j ++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 || j ==0) {
                        dp[i][j] = 1;
                    } else {
                        int min = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                        dp [i][j] = min;
                    }
                }
                if (dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result * result;
    }
}

分割类题型

No.1 Perfect Squares

题目：链接

解题思路：

dp[i] = Math.min(dp[i-1*1],dp[i-2*2],dp[i-3*3]...) + 1,这里注意dp常需要增加dp[0]的值便于回归

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1;i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i - j * j],dp[i]);
            }
            dp[i]++;
        }
        return dp[n];
    }
}

No.2 Decode Ways

题目：链接

解题思路：

本题要将情况细分：

如果是第一位是0，直接return 0
如果第一位不是0，dp[1]赋值为1
后续遇到0
如果和前面一位形成20,10,则dp[i] = dp[i-2]；
如果不是10，20，则可以直接return 0，这样的字符串找不到
如果后续不是0
如果和前面一位形成11到26之内，则这位即可以自己成为一个字母，也可以和前一位结合形成字母，即dp[i] = dp[i - 1] + dp[i-2]
反之则要单独为一个字母，即dp[i] = d[i-1]

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (s.charAt(0) == '0') return 0;
        dp[1] = 1;
        for (int i = 1; i < n; i++) {
            char c = s.charAt(i);
            char pre = s.charAt(i - 1);
            if (c == '0' && pre >= '1' && pre <= '2') {
                dp[i + 1] = dp[i - 1];
                dp[i] = dp[i - 1];
            } else if (c == '0') {
                return 0;
            } else if (pre == '1' || (pre == '2' && c >= '1' && c <= '6')) {
                dp[i + 1] = dp[i] + dp[i - 1];
            } else {
                dp[i + 1] = dp[i];
            }
        }
        return dp[n];
    }
}

No.3 Word Break

题目：链接

解题思路：

此题与分割完美平方数字类似，都是通过分割原来的input来做，不同的是完美平方数字是通过减去完美平方数字来获得上一个dp，而本题是获取到以当前i位置结尾的字符串，然后将其剪去获取上一dp，本质都是类似的。注意这里为了防止dict里的字符串互相包含的情况，需要每次都遍历dict中所有的字符串，根据其长度取上一个dp。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && s.substring(i - len,i).equals(word)) {
                    dp[i] = dp[i-len];
                    if (dp[i] == true) break;
                }
            }
        }
        return dp[n];
    }
}

No.4 Integer Break

题目：链接

思路解析：

第i个位置可以将其分解为两部分，其中每个部分再各自分为两部分，求dp。需要注意的是有可能i会>dp[i]，此时需要求max值，如果i>dp[i]就不分解了

class Solution {
    public int integerBreak(int n) {
        //dp[i] means output when input = i, e.g. dp[4] = 4 (2*2),dp[8] = 18 (2*2*3)...
        int[] dp = new int[n + 1];
        dp[1] = 1;
       // fill the entire dp array
        for (int i = 2; i <= n; i++) {
            //let's say i = 8, we are trying to fill dp[8]:if 8 can only be broken into 2 parts, the answer could be among 1 * 7, 2 * 6, 3 * 5, 4 * 4... but these numbers can be further broken. so we have to compare 1 with dp[1], 7 with dp[7], 2 with dp[2], 6 with dp[6]...etc
            for (int j = 1; j <= i / 2; j++) {
               // use Math.max(dp[i],....)  so dp[i] maintain the greatest value
                dp[i] = Math.max(dp[i],Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }
}

子序列问题

No.1 Longest Increasing Subsequence

题目：链接

解题思路：

这题还是要采用以i为结尾的数字的递增序列，不过要记录j再从后往前走，时间复杂度会是n²，有些大。这只是基本思路

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int result = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
            result = Math.max(result,dp[i]);
        }
        return result;
    }
}

进阶处理可以利用二分查找优化时间复杂度为n*logn，方法如下：

我们开创一个数组dp，将其视为一个stack，其每个位置dp[i]表示的是长度为i+1的子序列的最小结尾值，每次取nums[i]的时候更新dp数组，如果nums[i]更大，则直接入栈，如果nums[i]小，则向前二分查找到对应的dp赋值

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int j = 0;
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > dp[j]) {
                dp[++j] = nums[i];
            } else if (nums[i] < dp[j]) {
                int l = 0, r = j;
                while (l <= r) {
                    int m = l + (r - l) / 2;
                    if (dp[m] == nums[i]) {
                        break;
                    }
                    if (dp[m] < nums[i]) {
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                }
                if (l > r) {
                    dp[l] = nums[i];
                }
            }
        }
        return j + 1;
    }
}

No.2 Longest Common Subsequence

题目：链接

解题思路：

本题创建一个二维数组dp,其中i表示第一个字符串到i位置为止，j表示第二个字符串到j位置为止的最长的公共子序列长度。

即如果在位置ij，两个字符串对应的char相等，则dp[i][j]=dp[i-1][j-1] + 1，否则将等于dp[i-1[[j]和dp[i][j-1]的max

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        int x = 0, y = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1;j <= m; j++) {
                char a = text1.charAt(i - 1);
                char b = text2.charAt(j - 1);
                if (a == b) {
                    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[n][m];
    }
}

No.3 Delete Operation for Two Strings

题目链接：链接

解题思路：

和求最大common subseque一样，只要求出common subseque然后进行减法就可以

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char a = word1.charAt(i - 1);
                char b = word2.charAt(j - 1);
                if (a == b) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return m + n - dp[m][n] * 2;
    }
}

No.4 Maximum Length of Pair Chain

题目：链接

解题思路：

设置一个dp数组，dp[i]表示第i个位置能链接的最长值，每次从已经链接的头开始找起来，如果可以链接则dp[j]+1,

dp[i] = Math.max(dp[i],dp[j]+1)，可用二分加速

class Solution {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.sort(pairs,(a,b)->{return a[0] - b[0];});
        Arrays.fill(dp,1);
        for (int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
        }
    }

No.5 Wiggle Subsequence

题目：链接

解题思路：

考虑每种边界，如果是单调关系则覆盖，wiggle的时候就放在下一位

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n == 1) return 1;
        int[] stack = new int[n];
        int j = 0;
        stack[0] = nums[0];
        int isPositive = 0;
        for (int i = 1; i < n; i++) {
            if (isPositive == 0) {
                if (nums[i] > stack[j]) {
                    isPositive = 1;
                    stack[++j] = nums[i];
                } else if (nums[i] < stack[j]) {
                    isPositive = 2;
                    stack[++j] = nums[i];
                }
                continue;
            }
            if (isPositive == 1) {
                if (nums[i] > stack[j]) {
                    stack[j] = nums[i];
                } else if (nums[i] < stack[j]) {
                    stack[++j] = nums[i];
                    isPositive = 2;
                }
                continue;
            }
            if (isPositive == 2) {
                if (nums[i] < stack[j]) {
                    stack[j] = nums[i];
                } else if (nums[i] > stack[j]) {
                    stack[++j] = nums[i];
                    isPositive = 1;
                }
                continue;
            }
        }
        return j + 1;
    }
}

背包问题

背包分为0-1背包问题和完全背包问题

有 N 个物品和容量为 W 的背包，每个物品都有自己的价值 v 和体积 w，求拿那些物品可以使背包放下的价值最大

在0-1背包问题中公式为 dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w]+v),

因为i行的值只依赖于i-1行的值，所以可以去除i维度的dp数组，将其优化为一维数组，则公式为dp[j] = Math.max(dp[j],dp[j-w]+v)注意这时因为dp[j]受到dp[j-w]的影响，所以要从后往前计算，以免dp[j-w]更新导致dp[j]受影响

在完全背包问题中公式为dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w*1]+v*1,dp[i-1][j-w*2]+v*2,...),此时时间复杂度将很大，所以将其进行简化

可以想到dp[i][j] 在迭代时dp[i-1][j] 和dp[i][j-w]都已经得出结果，所以dp[i][j] = Math.max(dp[i-1][j],dp[i][j-w] +v)

同样的我们可以对dp[i][j]进行空间压缩，压缩后的公式为dp[j] = Math.max(dp[j],dp[j-w]+v)，注意此时因为j-w比j早一行，所以要正向遍历，确保j-w早于j位置更新

No.1 416. Partition Equal Subset Sum

题目：链接

解题思路：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        int n = nums.length;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = target; j >= nums[i - 1]; j--) {
                dp[j] = dp[j - nums[i - 1]] || dp[j];
            }
        }
        return dp[target];
    }
}

No.2 Ones and Zeroes

题目链接：链接

解题思路：

本题是一个三维数组，原三维代码如下：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        dp[0][0][0] = 0;
        for (int i = 1; i <= len; i++) {
            int zeroCount = 0;
            int oneCount = 0;
            for (int j = 0; j < strs[i - 1].length(); j ++) {
                char c = strs[i - 1].charAt(j);
                if (c == '0') {
                    zeroCount++;
                } else {
                    oneCount++;
                }
            }
            
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k ++) {
                    if (j < zeroCount || k < oneCount) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                         dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeroCount][k - oneCount] + 1);
                    }
                }
            }
            
        }
        return dp[len][m][n];
    }
}

将i维度去掉后，需要从后往前迭代，代码如下

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= len; i++) {
            int zeroCount = 0;
            int oneCount = 0;
            for (int j = 0; j < strs[i - 1].length(); j ++) {
                char c = strs[i - 1].charAt(j);
                if (c == '0') {
                    zeroCount++;
                } else {
                    oneCount++;
                }
            }
            
            for (int j = m; j >= zeroCount; j--) {
                for (int k = n; k >= oneCount; k --) {
                     dp[j][k] = Math.max(dp[j][k], dp[j - zeroCount][k - oneCount] + 1);
                }
            }
            
        }
        return dp[m][n];
    }
}

No.3 Coin Change

题目链接：链接

解题思路：

完全背包问题，二维数据如下：其中之所以初始化dp的所有值为 amount+1 是因为我们在取min，如果还是默认值就一直为0，设置为amount+1，最后如果遍历完还是amount+1则说明没找到返回-1。注意amount为0的时候要额外设置为0

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], amount + 1);
            dp[i][0] = 0;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= amount; j ++) {
                if (j < coins[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amount] == amount + 1 ? -1 : dp[n][amount];
    }
}

简化为一维数组，可以理解为我们对amount进行遍历，取min(dp[i],dp[i-coins[0]],dp[i-coins[1]....)

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i ++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i],dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

No.4 Target Sum

题目：https://leetcode.com/problems/target-sum/

解题思路：

这题可以化为一个0-1背包问题，target即为我们的目标值，每次选择是+还是-，用dp[i][j]表示在第i个位置，j表示当前计算出的值，dp[i][j]代表当前有多少种可能性。

可以得出公示为dp[i][j] = dp[i -1][j - nums[i]] + d[i-1][j+nums[i]]。

i的取值范围为0-len，j为从-sum到sum

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (Math.abs(target) > sum) return 0;
        int len = nums.length;
        int[][] dp = new int[len][2*sum + 1];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 2*sum + 1; j++) {
                if (i == 0) {
                    dp[i][j] = nums[i] == Math.abs(j - sum) ? (nums[i] == 0 ? 2 : 1 ) : 0;
                } else {
                    if (j - nums[i] >= 0){
                        dp[i][j] += dp[i - 1][j - nums[i]];
                    } 
                    if (j + nums[i] < 2 * sum + 1) {
                        dp[i][j] += dp[i - 1][j + nums[i]];
                    }
                }
            }
        }
        return dp[len - 1][target + sum];
    }
}

字符串编辑

No.1 Edit Distance

题目：链接

解题思路：

dp[i][j]为string1在i位置和string2在j位置情况下的最小操作数。

当 i == j时，dp[i][j] = dp[i-1][j-1]
i!=j
修改：dp[i][j] = dp[i-1][j-1]+1
插入i/删除j：dp[i][j] = dp[i][j-1] + 1
插入j/删除i：dp[i][j] = dp[i-1][j] + 1

注意在i = 0时，所有的dp[i][j]都为j，j=0时同理

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        if (n == 0) return m;
        if (m == 0) return n;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j ++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    char a = word1.charAt(i - 1);
                    char b = word2.charAt(j - 1);
                    if (a == b) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                    } 
                }
            }
        }
        return dp[n][m];
    }
}

No.2 2 Keys Keyboard

题目：链接

解题思路：

将第i位数字拆解为n*j，

class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        Arrays.fill(dp,n + 1);
        dp[0] = 0; dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i/j);
                }
            }
        }
        return dp[n];
    }
}

No.3 Regular Expression Matching

题目：链接

解题思路：

本题主要是在*号时比较难匹配，a*会匹配到""，"a"和"aaaaaaa*n"几种情况，分在字符串中几种又会有下面几种情况：

s为空的时候，此时只有*代表""才能匹配
s不为空的时候，如果遇到*
p[j - 1] == '.' || p[j -1] == s[i]
则说明此时 * 表示的是空，一个和n个都有可能，那么
对应*表示为空：dp[i][j] = dp[i][j - 2]
对应*表示一个：dp[i][j] = dp[i][j - 1]
对应*表示多个：dp[i][j] = dp[i -1][j]
p[j-1] != s[i]
说明此时*表示的一定为空

对应*表示为空：dp[i][j] = dp[i][j - 2]

代码如下：

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 2; i <= n; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pp = p.charAt(j - 1);
                char ss = s.charAt(i - 1);
                if (pp == '.' || pp == ss) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pp == '*') {
                    char ppp = p.charAt(j - 2);
                    if (ppp == '.' || ppp == ss) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

股票交易问题

冷却时间和交易费用等可以用dp的状态机实现

No.1 Best Time to Buy and Sell Stock

解题思路：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        int[] dp = new int[n];
        int result = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = prices[i] - prices[i - 1] + dp[i - 1] > 0 ? prices[i] - prices[i - 1] + dp[i - 1] : 0;
            result = Math.max(dp[i],result);
        }
        return result;
    }
}

No.2 Best Time to Buy and Sell Stock IV

解题思路：

如果k * 2>= n，则随意买卖
反之，建立俩动态规划数组，buy和sell，遍历每一天，探寻在第i天买卖第j次的收益，取max

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
        Arrays.fill(sell, 0);
        if (k * 2 >= n) {
            int result = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    result += prices[i] - prices[i - 1];
                }
            }
            return result;
        } 
        for (int i = 0; i < n; i ++) {
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j],sell[j - 1] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);
            }
        }
        return sell[k];
    }
}

No.3 Best Time to Buy and Sell Stock with Cooldown

题目链接：链接

解题思路：

这里制造三个状态节点：buy，sell，cooldown，遍历每天的股价，通过建立节点之间的方程来获得结果。

buy[i] = Math.max(buy[i-1],cool[i -1] - price[i]) // 本日不买和cooldown以后买入会让利润更高

sell[i] = buy[i - 1] + prices[i] //只有从昨日售出一条路

cool[i] = Math.max(cool[i - 1], sell[i - 1] //是维持昨日的cool不售出还是售出以后利润更高

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] buy = new int[n], sell = new int[n], cool = new int[n];
        buy[0] = -prices[0];
        sell[0] = cool[0] = 0;
        for (int i = 1; i < n; i ++) {
            buy[i] = Math.max(cool[i - 1] - prices[i], buy[i - 1]);
            sell[i] = buy[i - 1] + prices[i];
            cool[i] = Math.max(cool[i - 1], sell[i - 1]);
        }
        return Math.max(cool[n - 1], sell[n - 1]);
    }
}

No.4 Best Time to Buy and Sell Stock with Transaction Fee

题目：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

解题思路：、

创建状态机，分别有sell节点和buy节点

buy[i] = Math.max(buy[i -1], sell[i - 1] - prices[i]); // 当天不买入和当天买入收益

sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee); // 当天sell和当天不sell比收益

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[] buy = new int[n], sell = new int[n];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < n; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee);
        }
        return sell[n - 1];
    }
}

#刷题#