算法学习-动态规划

image.png

动态规划

算法描述

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要计算。 而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。

算法特点

1
2
3
4
这个问题的base case(最简单情况)是什么？  
这个问题有什么"状态"？
对于每个状态可以做什么选择使得状态发生改变？
如何定义dp数组/函数的含义来表现状态和选择？

算法关键

  • 最优子结构 opt[n]=best_of(opt[n-1],opt[n-2])
  • 存储中间状态: opt[i]
  • 递推公式(状态转移方程或DP方程) FIB: opt[i]=opt[n-1]+opt[n-2]   二位路径: opt[i,j]=opt[i-1][j]+opt[i][j+1]

算法框架

1
2
3
4
5
6
7
# 初始化base case
dp[0][0][...]=base case
# 进行状态转移
for 状态1 in 状态1所有值:
    for 状态2 in 状态2所有值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1,选择2,...)

列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

二分动规

动态规划结合二分查找，通过二分查找确定其上一个（如会议的结束时间）可选的值

相关题目
1751. 最多可以参加的会议数目 II
1235. 规划兼职工作

数位动规

https://oi-wiki.org/dp/number/

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

  1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
  3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
  4. 上界很大（比如 ），暴力枚举验证会超时。

数位 DP 的基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

接下来我们具体看几道题目。

https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/

例子参考

参考例子

参考资料

如何理解动态规划？ - 牛岱的回答 - 知乎

相关题目

动态规划

零钱兑换(medium)

动态规划、状态转移方程　F(S)=F(S-C)+1

例子2：假设
coins = [1, 2, 3], amount = 6

在上图中，可以看到：

1
2
3
4
5
F(3)=min(F(3−c1),F(3−c2),F(3−c3))+1
    =min(F(3−1),F(3−2),F(3−3))+1  
    =min(F(2),F(1),F(0))+1  
    =min(1,1,0)+1  
    =1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    //dp[i]表示凑成i金额的最少金币个数
    //那么每轮在遍历金币如果出现更大面额的金币就将其兑换
    //dp[i] = Math.min(dp[i-c]+1,dp[i]); for in coins
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);//填充
        dp[0] = 0;//basecase
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

零钱兑换 II（medium）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
//思路:动态规划
//dp[i]表示amount=i的coins可凑成总金额的方式;通过遍历不同的coin累计dp[i]的组成方式个数
//dp[j]=dp[i]+dp[j-coins[i]];
//dp[0]=1;
    
//1.为什么内层从coin开始 ? 因为i表示的是金额，如果 i<coin 此时是无法凑的
//2.为什么dp[i] = dp[i] + dp[i-c] ? dp[i]表示的是amount=i可以凑成的总数,那当前i大于等于新的coin,此时可以用c来凑出一直方式，那就是dp[i-c]
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0]=1;
        for(int coin:coins){
            for(int i=coin;i<=amount;i++){
                dp[i] = dp[i] + dp[i-coin];
            }
        }
        return dp[amount];
    }
}

斐波那契数列(easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= 1000000007;
        }
        return dp[n];
    }
    //空间优化
    public int fib(int n) {
        if(n<2)return n;
        int one = 0;
        int two = 1;
        for(int i=2;i<=n;i++){
            int temp = two;
            two = (one+two)%1000000007;
            one = temp;
        }
        return two;
    }
}

礼物的最大价值(medium)

[

](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof)
礼物的最大价值
题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例
输入:

[    
[1,3,1],
   [1,5,1],
   [4,2,1]
]

输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
解题思路
动态规划+dp数组，自底向上，状态转移方程 f(i, j) = max{f(i - 1, j), f(i, j - 1)} + grid[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;//获取数组长度
        int[] dp = new int[n + 1];//dp数组 最长长度为n+1 用于存放
        for (int i = 1; i <= m; i++) {//两层循环
            for (int j = 1; j <= n; j++) {
                dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1];//结合状态转移方程
            }
        }
        return dp[n];
    }
}

丑数(中等)

丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明

1是丑数。 n 不超过1690。

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
状态定义： 设动态规划列表 dp ，dp[i] 代表第 i + 1 个丑数。
转移方程：
当索引 a, b, c 满足以下条件时， dp[i] 为三种情况的最小值；
每轮计算 dp[i] 后，需要更新索引 a, b, c 的值，使其始终满足方程条件。
实现方法：分别独立判断 dp[i] 和 dp[a]×2 , dp[b]×3 , dp[c]×5 的大小关系，若相等则将对应索引 a , b , c 加 1 。

dp[a]×2>dp[i−1]≥dp[a−1]×2  
dp[b]×3>dp[i−1]≥dp[b−1]×3  
dp[c]×5>dp[i−1]≥dp[c−1]×5  

得出公式=dp[i] = min(dp[a]×2,dp[b]×3,dp[c]×5)

初始状态： dp[0] = 1 ，即第一个丑数为 1.  
返回值： dp[n-1] ，即返回第 n 个丑数.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //dp[i]表示第i个丑数
    //[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
    // 2, 3, 5分别定义三个指针 n2,n3,n5
    //dp[i] = Math.min(dp[n2]*2,dp[n3]*3,dp[n5]*5);
    //min值为当前指针时更新指针+1
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int n2 = 0,n3 = 0,n5 = 0;
        for(int i=1;i<n;i++){
            dp[i] = Math.min(dp[n2]*2,Math.min(dp[n3]*3,dp[n5]*5));
            if(dp[i]==2*dp[n2])n2++;
            if(dp[i]==3*dp[n3])n3++;
            if(dp[i]==5*dp[n5])n5++;
        }
        return dp[n-1];
    }
}

最长回文子串（中等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
思路：
1.首先对称有两种情况，分别是以一个字母为中心、两个字母为中心的回文子串。

暴力解法：枚举所有的情况（超时）
class Solution {
    public String longestPalindrome(String s) {
        int left = 0,length = 1;
        for(int i=0;i<s.length()-1;i++){
            for(int j=i+1;j<s.length();j++){
                if(isPalindrome(s,i,j)){
                    if(j-i+1>length){
                        length=j-i+1;
                        left=i;
                    }
                }
            }
        }
        //返回最大的
        return s.substring(left,left+length);
    }
    //是否是回文串
    public boolean isPalindrome(String s,int left,int right){
        while(left<right){
            if(s.charAt(left)!=s.charAt(right))return false;
            left++;
            right--;
        }
        return true;
    }
}

中心扩散法:如果一个字符串是回文串，那么去掉头尾的两个依然是回文串。从中心向两边扩散（分为两种情况，一个字符为中心和两个字符为中心）
class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<2)return s;
        int maxLength = 1;int beginIndex = 0;
        for(int i=0;i<s.length();i++){
            int len1 = centerSpread(s,i,i);//一个字母为中心
            int len2 = centerSpread(s,i,i+1);//两个字母为中心
            int currMax = Math.max(len1,len2);
            if(currMax>maxLength){
                // 根据i和currMax算begin下标
                // 奇数：i-currMax/2
                // 偶数：i-currMax/2+1
                // 统一：i-(currMax-1)/2
                beginIndex = i - (currMax - 1)/2;
                maxLength=currMax;
            }
        }
        return s.substring(beginIndex,beginIndex+maxLength);
    }
    //aba abba
    public int centerSpread(String s,int left,int right){
        while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        //right-left+1-2=right-left-1;
        return right-left-1;
    }
}

动态规划：

dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;
        int maxLen = 1;
        int begin = 0;
        char[] cs = s.toCharArray();
        // dp[i][j]:表示s[i][j]是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：单独一个字符肯定是回文子串
        for (int i = 0; i < len; i++) dp[i][i] = true;
        // 经验：dp区域是正方形的话，通常左下角区域无效不需要再填，因为走过的区域不用再走
        for (int j = 1; j < len; j++) { // 上三角区域，按列从上到下填
            for (int i = 0; i < j; i++) {
                // 首尾不相等时，必不是回文串
                if (cs[i] != cs[j]) {
                    dp[i][j] = false;
                } else {
                    // 首尾相等时，有2种情况
                    // 情况1：s[i...j]长度不超过3，不用检查必为回文串
                    // 情况2：s[i...j]长度大于3，由s[i+1...j-1]来判断
                    dp[i][j] = j - i + 1 <= 3 || dp[i + 1][j - 1];
                }
                // 更新max和begin
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

最长公共子序列(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    //dp[i][j]表示text1以i结尾,text2以j结尾的最长公共子序列长度

    //二维表
    //  abcde
    // 000000
    //a011111
    //c011222
    //e011223

    //dp[i][j] = dp[i-1][j-1]+1  (text1[i]==text2[j])
    //dp[i][j] = dp[i][j-1] (text1[i]!=text2[j])
    //dp[i][j] = dp[i-1][j] (text1[i]!=text2[j])
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int ret = 0;
        int[][] dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                char c1 = text1.charAt(i-1);
                char c2 = text2.charAt(j-1);
                if(c1==c2)dp[i][j] = dp[i-1][j-1]+1;
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j]);
                dp[i][j] = Math.max(dp[i][j-1],dp[i][j]);
            }
        }
        return dp[m][n];
    }
}

最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //dp[i]表示以i结尾的最长递增子序列
    //每轮以nums[i]结尾作为增长序列进行计算，计算n轮即可得出
    //dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int max = 1;
        int[] dp = new int[n];
        dp[0] = 1;//base case
        for (int i = 1; i < n; i++) {
            dp[i] = 1;//最后一个为必取
            for (int j = 0; j < i; j++) {
                //必须是nums[i]大于nums[j]（前面的数）才能累计
                if (nums[i]>nums[j])dp[i] = Math.max(dp[i],dp[j]+1);
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

不同路径(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //dp方程 dp[i][j]=dp[i+1][j]+dp[i][j+1]
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][n-1]=1;
        for (int i = 0; i < n; i++) dp[m-1][i]=1;
        for (int i = m-2; i >=  0; i--) {
            for (int j = n-2; j >= 0; j--) {
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[0][0];
    }
    //自顶向下 dp[i][j]=dp[i-1][j]+dp[i][j-1]
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++)dp[i][0] = 1;
        for(int i=0;i<n;i++)dp[0][i] = 1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

不同路径 II(中等)

一维数组压缩状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {//且没有障碍的时候在推导
                    f[j] += f[j - 1];
                }
            }
        }
        return f[m - 1];
    }
}

复杂度分析

  • 时间复杂度：O(nm)O(nm)，其中 nn 为网格的行数，mm 为网格的列数。我们只需要遍历所有网格一次即可。
  • 空间复杂度：O(m)O(m)。利用滚动数组优化，我们可以只用 O(m)O(m) 大小的空间来记录当前行的 ff 值。

最长公共子序列(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int  longestCommonSubsequence(String text1, String text2) {
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int length1 = t1.length;
        int length2 = t2.length;
        int[][] dp = new int[length1+1][length2+1];
        //求dp
        for (int i = 1; i < length1 +1; i++) {
            for (int j = 1; j < length2 +1; j++) {
                if (t1[i-1] == t2[j-1]){
                    // 这边找到一个 lcs 的元素，继续往前找
                    dp[i][j] = 1+ dp[i-1][j-1];
                }else {
                    //谁能让 lcs 最长，就听谁的
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[length1][length2];
    }
}

最大子序和(简单)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

状态转移方程 f(i)=max{f(i−1)+nums[i],nums[i]}

1
2
3
4
5
6
7
8
9
10
class Solution {
    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;
    }
}

乘积最大子数组(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    //dp[i][0]表示以i结尾的乘积最大值
    //dp[i][1]表示以i结尾的乘积最小值
    //dp[i][0]=Math.max(nums[i],dp[i-1][1]*nums[i],dp[i-1][0]*nums[i])
    //dp[i][1]=Math.min(nums[i],dp[i-1][1]*nums[i],dp[i-1][0]*nums[i])
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] maxF = new int[length];
        int[] minF = new int[length];
        System.arraycopy(nums, 0, maxF, 0, length);
        System.arraycopy(nums, 0, minF, 0, length);
        for (int i = 1; i < length; ++i) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
    //优化
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }
}

删除并获得点数(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        //找出最大值
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        //构建数组(每个数有的个数)
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

回文串(中等)

思路1:中间向两边扩散，遍历字符数组，时间复杂度O(n^2)

思路2:对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。
得出状态转移方程 P(i,j)=P(i+1,j−1)∧(Si==Sj)也就是说，只有 s[i+1:j-1]s[i+1:j−1] 是回文串，并且 ss 的第 i 和 j 个字母相同时，s[i:j]s[i:j] 才会是回文串。时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Solution {

    //dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
    public String longestPalindrome(String s) {
        int len = s.length();
        //特殊情况
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度（先一列一列的填，在一行一行填）
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }
                //如果字符不相等
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    //
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

马拉车算法

最长定差子序列(中等)

我们从头遍历数组，遇到一个数 x，判断 x-d 在不在数组里面即可知道，能不能形成以 x 为结尾的等差数组，同时，我们记录下来以 x 结尾的等差数组的长度，这样，在后续的遍历过程中，我们就可以使用得上这个长度了。

我们来举个例子，假设给定数组为 [1,5,3,6,5,7]，等差 d=2，辅助数组为 dp，求解的过程如下：
遍历到 1，发现 1-2=-1 不在 dp 数组，记录 dp[1] = 1，表示以 1 结尾的等差数列只有 1 个数；
遍历到 5，发现 5-2=3 不在 dp 数组，记录 dp[5]=1；
遍历到 3，发现 3-2=1 在 dp 数组且以 1 结尾的等差数列长度为 1，所以，记录 dp[3]=dp[3-2]+1=2，表示以 3 结尾的等差数列长度为 2；
遍历到 6，发现 6-2=4 不在 dp 数组，记录 dp[6]=1；
遍历到 5，发现 5-2=3 在 dp 数组，记录 dp[5]=dp[5-2]+1=3；
遍历到 7，发现 7-2=5 在 dp 数组，记录 dp[7]=dp[7-2]+1=4；
取 dp 数组中的最大值，即 4，所以，最长等差子序列的长度为 4。
这其实就是动态规划的递推过程，所以，我们可以定义动态规划如下：
状态定义：dp[x] 表示以 x 结尾的最长等差子序列的长度；
状态转移：dp[x]=dp[x-d]+1；
初始值：无；

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int ans = 0;
        Map<Integer, Integer> dp = new HashMap<Integer, Integer>();
        for (int v : arr) {
            dp.put(v, dp.getOrDefault(v - difference, 0) + 1);
            ans = Math.max(ans, dp.get(v));
        }
        return ans;
    }
}

分割等和子集(中等)

思路:

转化为求当前数组元素和==所有元素和/2，进一步转化为背包问题，将数组元素装入total_sum/2的背包中，通过动态规划求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}

戳气球 (hard)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
思路:
dp[i][j] 表示开区间 (i,j) 能拿到的的金币，k是这个区间 最后一个 被戳爆的气球，枚举i和j，
遍历所有区间。

i-j能获得的最大数量的金币=戳破当前的气球获得的金钱+之前i-k、k-j区间中已经获得的金币

dp[i][j]=max(dp[i][j],dp[i][k]+val[i] * val[k] * val[j]+dp[k][j])

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 2][n + 2];
        int[] val = new int[n + 2];
        val[0] = val[n + 1] = 1;//边界
        for (int i = 1; i <= n; i++) {//初始化
            val[i] = nums[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += dp[i][k] + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], sum);
                }
            }
        }
    return dp[0][n + 1];
    }
}

198. 打家劫舍（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    //dp方程：dp[i]=max(dp[i-1],dp[i-2]+num[i])
    public int rob(int[] nums) {
        if(nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        //dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        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];
    }
}

打家劫舍II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    //因为围成了圈，分为两种情况，抢了第一个，最后一个就不能抢了
    public int rob(int[] nums) {
        if(nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        if(nums.length==2)return Math.max(nums[0],nums[1]);
        return Math.max(
            robRange(0,nums.length-2,nums),//可取第一个进行计算,不取最后一个
            robRange(1,nums.length-1,nums)//可取最后一个进行计算,不取第一个
        );
    }
    public int robRange(int start,int end,int[] nums){
        int one = nums[start];
        int second =Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++){
            int temp = second;
            second = Math.max(one+nums[i],second);
            one = temp;
        }
        return second;
    }
}

打家劫舍III (medium)

其核心思想还是不能取相临的节点，针对某个节点有两种选择 打劫或者不打劫，当前打劫下一个节点就不能打劫。通过dfs遍历树，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int rob(TreeNode root) {
    int[] rootStatus = dfs(root);
    return Math.max(rootStatus[0], rootStatus[1]);
}

public int[] dfs(TreeNode node) {
    if (node == null)return new int[]{0, 0};//arr[0]抢，arr[1]不抢
    int[] l = dfs(node.left);
    int[] r = dfs(node.right);
    //选择当前节点=当前节点+左边子节点不抢+右边子节点不抢
    int selected = node.val + l[1] + r[1];
    //不选择当前节点，就可以抢或者不抢左右子节点
    int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
    return new int[]{selected, notSelected};
}

买卖股票 （easy）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    //贪心
    public int maxProfit(int[] prices) {
        int minPrices = Integer.MAX_VALUE;
        int maxProfit = 0;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<minPrices)minPrices=prices[i];
            else if(prices[i]-minPrices>maxProfit){
                maxProfit=prices[i]-minPrices;
            }
        }
        return maxProfit;
    }
    // dp[i][2] 表示第i天获得的最大利润

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

    //今天卖出或者昨天卖出
    // dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0])  
    //                      dp[i-1][1]+prices[i]表示前一天持股今天卖出+prices[i]
    //                      dp[i-1][0]表示前一天就已经卖出不持股
    
    //今天买入或者昨天买入
    // dp[i][1] = Math.max(dp[i-1][1],-prices[i])
    //                      dp[i-1][1] 表示前一天买入后手上拥有的现金数
    //                      -prices[i] 表示今天买入后手上拥有的现金数
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n<2)return 0;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[n-1][0];
    }

}

买卖股票II（medium）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    //dp
    //要么买入股票，要么卖出得到现金。买入股票需要前一天已经卖出，所以如果买入比较 （前一天卖出得到的钱-今天买入话的钱）再和昨天如果买入dp[i-1][1]取拥有max现金的
    //定义状态
    //dp[i][j] 表示到下标为i的这一天，持股状态为j时，我们手上拥有的最大现金数。j=0持有现金，j=1表示持有股票
    //dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) max(昨天卖出股票后拥有的现金,昨天买入股票后拥有的现金+今天卖出得的现金)
    //dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]) max(昨天买入股票拥有的现金,昨天持有现金拥有的现金-今天买入股票花费的现金)
    public int maxProfit(int[] prices) {
    	int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++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], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];//持有现金
    }
    //贪心：有利可图就卖出
    public int maxProfit(int[] prices) {
        int ans = 0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]-prices[i-1]>0){
                ans+=prices[i]-prices[i-1];
            }
        }
        return ans;
    }
}

买卖股票的最佳时机 III (hard)

思路：动态规划

每一天结束之后，有可能处于以下五种状态之一：

  • 没有买股也没有卖股。
  • 买了第一支股，但是还没有卖出第一支股。
  • 买了第一支股，并且卖出第一支股。
  • 买了第一支股，并且卖出第一支股，买了第二支股，但是还没有卖出第二支股。
  • 买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股。
  • 我们可以遍历 prices 数组，模拟第 i 天的情况。计算出第 i 天五种情况利润的最大值。

1.对于第一种情况，利润始终为 0。

2.对于第二种情况，由于还没有盈利，只买进了某支股，为亏损状态。此时，亏损的最小值是 prices[0] 至 prices[i] 的最小值，假设为 buy1。可以看做，第二种情况利润的最大值为：-buy1。

状态转移方程为：buy1 = max(buy1, -prices[i]);

3.对于第三种情况，利润的计算需要在第二种情况的基础上再卖出一支股。所以需要先计算第二种情况，再在遍历到 prices[i] 的时候，判断要不要卖出。如果在以最小的亏损买入第一支股的情况下，卖出当前这支股所得利润最大，则卖出当前这支股。

状态转移方程为：sell1 = max(sell1, prices[i] + buy1);

注意这里是 prices[i] + buy1，不是 prices[i] - buy1，因为 buy1 是负值，代表利润。

4.对于第四种情况，不能直接买入，因为有可能第一支股还没卖出。利润的计算需要在第三种情况的基础上再买入一支股。所以需要先计算第三种情况，再在遍历到 prices[i] 的时候，判断要不要买入。如果在卖出第一支股所得利润最大的情况下，买入当前这支股最终所得利润最大，则买入当前这支股。

状态转移方程为：buy2 = max(buy2, sell1 - prices[i]);

5.对于第五种情况，利润的计算需要在第四种情况的基础上再卖出一支股。所以需要先计算第四种情况，再在遍历到 prices[i] 的时候，判断要不要卖出。如果在卖出第一支股然后买入第二支股所得利润最大的情况下，卖出当前这支股所得利润最大，则卖出当前这支股。

状态转移方程为：

状态转移方程为：sell2 = max(sell2, prices[i] + buy2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
//一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过

//所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]

//具体一天结束时的6种状态：

//未持股，未卖出过股票：说明从未进行过买卖，利润为0
//dp[i][0][0]=0
//未持股，卖出过1次股票：可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）
//dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])
//未持股，卖出过2次股票:可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）
//dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])
//持股，未卖出过股票：可能是今天买的，也可能是之前买的（昨天也持股）
//dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])
//持股，卖出过1次股票：可能是今天买的，也可能是之前买的（昨天也持股）
//dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])
//持股，卖出过2次股票：最多交易2次，这种情况不存在
//dp[i][1][2]=MIN_VALUE
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n][2][3];
        int MIN_VALUE = Integer.MIN_VALUE / 2;
        //第一天休息
        dp[0][0][0]=0;
        //第一天买入
        dp[0][1][0]=-prices[0];
        //第一天不可能已经有卖出
        dp[0][0][1] = MIN_VALUE;
        dp[0][0][2] = MIN_VALUE;
        //第一天不可能已经卖出
        dp[0][1][1] = MIN_VALUE;
        dp[0][1][2] = MIN_VALUE;

        for(int i=1;i<n;i++){
            dp[i][0][0]=0;
            dp[i][0][1]=Math.max(dp[i-1][1][0]+prices[i],dp[i-1][0][1]);
            dp[i][0][2]=Math.max(dp[i-1][1][1]+prices[i],dp[i-1][0][2]);
            dp[i][1][0]=Math.max(dp[i-1][0][0]-prices[i],dp[i-1][1][0]);
            dp[i][1][1]=Math.max(dp[i-1][0][1]-prices[i],dp[i-1][1][1]);
            dp[i][1][1]=Math.max(dp[i-1][0][1]-prices[i],dp[i-1][1][1]);
            dp[i][1][2]=MIN_VALUE;
        }
        return Math.max(0,Math.max(dp[n - 1][0][1], dp[n - 1][0][2]));
    }
}

买卖股票的最佳时机 IV (hard)

买卖股票的最佳时机含手续费

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    //买入 dp[i][0] =  max(dp[i-1][0],dp[i-1][1]+prices[i])
    //卖出 dp[i][1] =  max(dp[i-1][1],dp[i-1][0]-prices[i]-fee)
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<prices.length;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],(dp[i-1][0]+prices[i])-fee);
        }
        return dp[prices.length-1][1];
    }
}

最佳买卖股票时机含冷冻期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int n = prices.length;
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        int[][] f = new int[n][3];
        f[0][0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            //
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
            f[i][1] = f[i - 1][0] + prices[i];
            f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
        }
        return Math.max(f[n - 1][1], f[n - 1][2]);
    }
}

参考大佬的题解：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/mai-mai-gu-piao-wen-ti-by-chen-wei-f-xvs1/
image.png
状态转移方程
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
//冷却时间1天，所以要从 i - 2 天转移状态
//买入，卖出 —- 冷冻期 —- 买入，卖出
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
题目不限制k的大小，可以舍去
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])
//降维i
dp[0] = Math.max(dp[0], dp[1] + prices[i])
dp[1] = Math.max(dp[1], profit_freeze - prices[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
const maxProfit = function (prices) {
    let n = prices.length;
    let buy = -prices[0];//手中有股票
    let sell = 0;//没有股票
    let profit_freeze = 0;
    for (let i = 1; i < n; i++) {
        let temp = sell;
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, profit_freeze - prices[i]);
        profit_freeze = temp;
    }
    return sell;
};

最大子数组和（easy）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //dp[i]表示以第nums[i]结尾的最大取值
    //dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
    //在遍历过程中共两种选择：
    // 1.在当前数组中选择当前的数 dp[i-1]+nums[i]
    // 2.在当前数组中不选择当前的数，那当前的数作为新一轮的数组第一个元素 nums[i]
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ret = dp[0];
        for(int i=1;i<n;i++){
            int cur = dp[i-1]+nums[i];
            dp[i] = nums[i] > cur ? nums[i] : cur;
            ret = ret > dp[i] ? ret :dp[i];
        }
        return ret;
    }
}

编辑距离

举个例子，word1 = “abcde”, word2 = “fgh”,我们现在算这俩字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：

  1. 知道”abcd”变成”fgh”多少步（假设X步），那么从”abcde”到”fgh”就是”abcde”->”abcd”->”fgh”。（一次删除，加X步，总共X+1步）
  2. 知道”abcde”变成“fg”多少步（假设Y步），那么从”abcde”到”fgh”就是”abcde”->”fg”->”fgh”。（先Y步，再一次添加，加X步，总共Y+1步）
  3. 知道”abcd”变成“fg”多少步（假设Z步），那么从”abcde”到”fgh”就是”abcde”->”fge”->”fgh”。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    //word1变成word2最少操作步骤
    //
    //dp[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离
    //dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))
    class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            if(m*n==0)return m+n;
            //dp[i][j]表示 word1[0..i] 转为为 word2[0...j] 所使用的最少操作数
            int[][] dp = new int[m+1][n+1];
            //初始化(""转为其他字符串(abc)的操作数为len(abc))
            for(int i=0;i<=n;i++)dp[0][i]=i;
            for(int i=0;i<=m;i++)dp[i][0]=i;
            //递推dp
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    int delete = dp[i-1][j]+1;
                    int add = dp[i][j-1]+1;
                    int replace = dp[i-1][j-1];
                    if(word1.charAt(i-1)!=word2.charAt(j-1))replace++;
                    dp[i][j]=Math.min(replace,Math.min(add,delete));
                }
            }
            return dp[m][n];
        }
    }
    class Solution {
        
    // dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
    // 所以，
    // 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
    // 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    // 其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
    // 注意，针对第一行，第一列要单独考虑
        public int minDistance(String word1, String word2) {
           int m = word1.length();
            int n = word2.length();
            int[][] dp = new int[m+1][n+1];
            for (int i = 0; i <= m; i++) dp[i][0] = i;
            for (int i = 0; i <= n; i++) dp[0][i] = i;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                    else dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
                }
            }
            return dp[m][n];
        }
    }

统计元音字母序列的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    //已知:
    //每个元音 'a' 后面都只能跟着 'e'
    //每个元音 'e' 后面只能跟着 'a' 或者是 'i'
    //每个元音 'i' 后面 不能 再跟着另一个 'i'
    //每个元音 'o' 后面只能跟着 'i' 或者是 'u'
    //每个元音 'u' 后面只能跟着 'a'
    //
    //可知:
    //每个元音 'a' 前面 'u','e','i'
    //每个元音 'e' 前面 'a','i'
    //每个元音 'i' 前面 'o','e'
    //每个元音 'o' 前面 'i',
    //每个元音 'u' 前面 'o','i'
    //dp[i][j]标识长度为i，元音j结尾的个数
    //dp[i][0] = dp[i-1][4] + dp[i-1][1] + dp[i-1][2]
    //dp[i][1] = dp[i-1][0] + dp[i-1][2]
    //dp[i][2] = dp[i-1][3] + dp[i-1][1]
    //dp[i][3] = dp[i-1][2]
    //dp[i][4] = dp[i-1][2] + dp[i-1][3]
    public int countVowelPermutation0(int n) {
        long mod = 1000000007;
        long[][] dp = new long[n+1][5];
        for(int i=0;i<5;i++)dp[1][i]=1;
        for(int i=2;i<n+1;i++){
            dp[i][0] = (dp[i-1][4] + dp[i-1][1] + dp[i-1][2])%mod;
            dp[i][1] = (dp[i-1][0] + dp[i-1][2])%mod;
            dp[i][2] = (dp[i-1][3] + dp[i-1][1])%mod;
            dp[i][3] = (dp[i-1][2])%mod;
            dp[i][4] = (dp[i-1][2] + dp[i-1][3])%mod;
        }
        return (int)((dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]+dp[n][4])%mod);
    }
    //dp优化空间
    public int countVowelPermutation(int n) {
        long mod = 1000000007;
        long a = 1, e = 1, i = 1, o = 1, u = 1;
        for (int k = 2; k < n + 1; k++) {
            long ap = a,ep = e,ip = i,op = o,up = u;
            a = (up + ep + ip) % mod;
            e = (ap + ip) % mod;
            i = (op + ep) % mod;
            o = ip % mod;
            u = (ip + op) % mod;
        }
        return (int) ((a + e + i + o + u) % mod);
    }
}

最长重复子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //dp[i][j]表示以nums1[i]结尾nums2[j]结尾的最长重复子数组
    //dp[i][j] = Math.max(0,dp[i-1][j-1]+1 && nums1[i]==nums2[j])
    
    //dp[i][j]表示以nums1[i]结尾和nums2[j]结尾的最长重复数组
    //  1,2,3,2,1]
    //3,0,0,1,0,0
    //2,0,1,1,2,0
    //1,1,0,0,2,3
    //4,0,0,0,0,0
    //7,0,0,0,0,0
    //如果碰到了不等于的，那从这个不等于的位置就要从0开始计了，这一点和求公共子序列不同
    //dp[i][j] = max(dp[i-1][j-1]+(A[i-1] == B[j-1]?1:0),dp[i-1][j],dp[i][j-1])
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}

最长有效括号（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//1.我们只有遇到')'的时候才有必要去计算
//2.每两个字符检查一次：
//2.1 “()”的情况,当前')'与s[i-1]构成有效括号,dp[i]=dp[i-2]+2
//2.2 “))”的情况,s[i-1]==')',需要判断，s[i-1]是否与前面的构成有效括号，否则s[i]无法构成有效括号。
//		这时，我们只需要找到和s[i]配对对位置，并判断其是否是 '(' 即可。和其配对的位置为：i-dp[i−1]-1。
//	（因为dp[i-1]表示的是[0,i-1]的有效括号个数,使用i-dp[i-1]得出第一位有效括号的下标，-1则获取前面一位，如"))(())",dp[4]=2, 5-dp[4]-1=2,dp[5]=dp[4]+dp[2]+2)
//	  如果s[i-dp[i-1]-1]='('则 dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2
class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

221. 最大正方形（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //dp[i][j]表示以[i][j]下标正方形的边长
    //dp[i][j]=min(dp[i-1][j-1] , dp[i-1][j] , dp[i][j-1])
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int ret = 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(i==0||j==0) dp[i][j] = 1;
                    else dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
        }
        return ret*ret;
    }
}

单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    //dp[i] 表示以i结尾的字符串是否能被wordDict拆分
    //dp[i] = dp[j]+wordDict.contains(s(j,i));
    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(int j=0;j<i;j++){
                if(dp[j]&&wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

解码方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    //dp[i]表示以i下标结尾的s的编码总数
    //如果s[i]能解码 dp[i]=dp[i-1]
    //如果s[i]和s[i-1]能组成 dp[i]+=dp[i-2]
    //dp[i] = dp[i-1] + dp[i-2] ((1<=s[i-2,i]<=26))
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            if(s.charAt(i-1)!='0'){
                dp[i]+=dp[i-1];
            }
            if(i>1&&(s.charAt(i-2)=='1'||(s.charAt(i-2)=='2'&&s.charAt(i-1)<='6'))){
                dp[i]+=dp[i-2];
            }
        }
        return dp[n];
    }
    //思路：回溯（超时）
    private int count;
    public int numDecodingsByBacktrack(String s) {
        //backtrack(s,0);
        return count;
    }
    public void backtrack(String s,int index){
        if(index==s.length()){
            count++;
            return;
        }
        if(index<s.length()&&s.charAt(index)!='0'){
            backtrack(s,index+1);
        }
        if(index<s.length()-1&&s.charAt(index)!='0'){
            int x = 0;
            for(int i=index;i<index+2;i++)x = x * 10 + s.charAt(i)-'0';
            if(x>=1&&x<=26)backtrack(s,index+2);
        }
    }
}

正则表达式匹配

dp[i][j]表示s[0…i] p[0..j] 是否匹配

  • 遇到 p[j] == ‘‘ 时判断dp[i][j-2]是否匹配（注意’‘表示*前面的字符有0个或多个），

1.当dp[i][j-2] = true 时，则 dp[i][j] = true
2.当dp[i][j-2] = false 时，如果 s[i-1]==true &&(s[i]==p[i-1] || p[i-1]==’.’) 则 dp[i][j] = true

  • 遇到 p[j] == ‘.’ 取 dp[i][j] = dp[i-1][j-1]
  • 遇到 s[i]==p[j] 取 dp[i][j] = dp[i-1][j-1]
  • 遇到 s[i]!=p[j] 即 dp[i][j] = false

dp表

A . * B B A
T F F F F F F
A F T F T F F F
B F F T T T F F
B F F F T T T F
A F F F T F F T
A F F F T F F F
A F F F T F F F 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    //dp[i][j]表示s[0...i] p[0..j] 是否匹配
    // 遇到 p[j] == '*' 时判断dp[i][j-2]是否匹配（注意'*'表示*前面的字符有0个或多个），
    //  1.当dp[i][j-2] = true 时，则 dp[i][j] = true
    //  2.当dp[i][j-2] = false 时，如果 s[i-1]==true &&(s[i]==p[i-1] || p[i-1]=='.') 则 dp[i][j] = true (即f[i-1][j])
    //遇到 p[j] == '.' 取 dp[i][j] = dp[i-1][j-1]
    //遇到 s[i]==p[j] 取 dp[i][j] = dp[i-1][j-1]
    //遇到 s[i]!=p[j] 即 dp[i][j] = false
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        //init
        dp[0][0] = true;
        //dp
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p.charAt(j-1) == '*'){
                    dp[i][j] = dp[i][j-2];
                    if(matches(s,p,i,j-1))dp[i][j] = dp[i][j]||dp[i-1][j];
                }else{
                    if(matches(s,p,i,j))dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
    public boolean matches(String s,String p,int i,int j){
        if(i==0)return false;
        if(p.charAt(j-1)=='.')return true;
        return s.charAt(i-1) == p.charAt(j-1);
    }
}

44. 通配符匹配（hard)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 = 1; i <= n; ++i) {
            if (p.charAt(i - 1) == '*') dp[0][i] = true;
            else break;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

骑士在棋盘上的概率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //思路:dp[step][i][j]表示骑士从棋盘上的点 (i,j) 出发，走了 step 步时仍然留在棋盘上的概率
    //dp[step][i][j] = (1/8)(∑dp[step−1][i+di][j+dj])  其中(di,dj) 表示走法对坐标的偏移量如下的dirs
    //dp[0][i][j]=1;
    private int[][] dirs = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k + 1][n][n];
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (int[] dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
}

三角形最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    //自顶向下
    //dp[i][j] 表示从三角形顶部走到位置(i,j) 的最小路径和。这里的位置(i,j) 指的是三角形中第 i 行第 j 列（均从 0 开始编号）的位置。
    //上一步就只能在位置 (i−1,j−1) 或者位置 (i−1,j)
    //dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
    public int minimumTotal0(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);//直接从i-1开始免去前面不必要的计算
            for (int j = 1; j < i; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);//最后一个只能取上一行的最后一个
        }  
        int totalMin = dp[n-1][0];
        for(int i=0;i<n;i++)totalMin=Math.min(totalMin,dp[n-1][i]);
        return totalMin;
    }
    //自底向上
    //dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
        int[][] dp = new int[n + 1][n + 1];
        // 从三角形的最后一行开始递推。
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

鸡蛋掉落

转移的状态有: k鸡蛋个数，n为楼层，所以dp为二维数组，dp[k][n] = m 当前状态为 k 个鸡蛋，面对 n 层楼# 这个状态下最少的扔鸡蛋次数为 m

  • 如果鸡蛋碎了，那么鸡蛋的个数 K 应该减一，搜索的楼层区间应该从 [1..N] 变为 [1..i-1] 共 i-1 层楼；
  • 如果鸡蛋没碎，那么鸡蛋的个数 K 不变，搜索的楼层区间应该从 [1..N] 变为 [i+1..N] 共 N-i 层楼。

dp[k][n] = dp[k][n - 1] + dp[k - 1][n - 1] + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
  int superEggDrop(int K, int N) {
    // m 最多不会超过 N 次（线性扫描）
    int[][] dp = new int[K + 1][N + 1];
    // base case:
    // dp[0][..] = 0
    // dp[..][0] = 0
    // Java 默认初始化数组都为 0
    int m = 0;
    while (dp[K][m] < N) {
        m++;
        for (int k = 1; k <= K; k++)
            dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
    }
    return m;
  }
}

不同的二叉搜索树（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    //以每个节点作为根节点，[1,i)作为左子树，(i,n]作为右子树，进行构建不同的二叉搜索树
    //其左右子树又可以采用此方式进行构建不同的二叉搜索树,可转化为子问题，由此可采用动态规划
    //则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积
    //dp[i]+=dp[j-1]*dp[i-j] j=[1,i] i=[2,n+1]
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        //basecase
        dp[0] = 1;
        dp[1] = 1;
        //dp[i]+=dp[j-1]*dp[i-j] j=[1,i] i=[2,n+1]
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
    //数学：卡塔兰数
    public int numTrees(int n) {
        // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);//卡塔兰数公式
        }
        return (int) C;
    }
}

交错字符串（mid）

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否能构成 s3 的前 i+j 个字符
//画出如上dp二维表
public static boolean isInterleave(String s1, String s2, String s3) {
    int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
    //不满足直接返回
    if (l1 + l2 != l3)  return false;
    //dp数组
    boolean[][] dp = new boolean[l1 + 1][l2 + 1];
    //basecase
    dp[0][0] = true;
    //dp[i][j] = true (s3.charAt(i-1)==s1.charAt(i-1) && dp[i-1][0] and 0<i<s1.length)
    //dp[i][j] = true (s3.charAt(i-1)==s2.charAt(i-1) && dp[0][i-1] and 0<i<s2.length)
    for (int i = 1; i < l1 + 1; i++) {
        dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    }
    for (int i = 1; i < l2 + 1; i++) {
        dp[0][i] = dp[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);
    }
    //dp[i][j] = (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
    for (int i = 1; i < l1 + 1; i++) {
        for (int j = 1; j < l2 + 1; j++) {
            dp[i][j] = (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
        }
    }
    return dp[l1][l2];
}

343. 整数拆分（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    //数学
    public int integerBreak(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
    //dp[i]表示整数i对应的最大乘积
    //将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)
    //将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]
    //dp[i] = Max(dp[i],j*(i-j),j*dp[i-j]) j=[1,i-1]
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i=2;i<=n;i++){
            for(int j=i-1;j>=1;j--){
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}

673. 最长递增子序列的个数（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    //dp[i]表示以nums[i]结尾的最长递增子序列，dp[j]表示[0,i)时
    //dp[i] = Math.max(dp[i],dp[j]+1) i for (0,n-1), j for (0,i)
    //本题求的是最长递增子序列个数，不是长度
    //在基于长度的算法上通过记录其最长长度的个数即可
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if(n<=1)return n;
        int[] dp = new int[n];
        int[] count = new int[n];
        for(int i=0;i<n;i++)dp[i] = count[i] = 1;//初始化默认最少1
        int max = 0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                //如果nums[i]>nums[j]则说明当前j可取
                if(nums[i]>nums[j]){
                     //dp[j]+1>dp[I]则说明当前去nums[j]会比dp[i]大，增加最长长度
                    if(dp[j]+1>dp[I]){
                        dp[i] = dp[j]+1;
                        count[i] = count[j];//更新最长子序列个数为count[j]
                    }else if(dp[j]+1==dp[i]){如果dp[j]+1==dp[I]则存在相同长度的递增子序列
                        count[i]+=count[j];//合计两个长度一样的个数
                    }
                }
            }
            max = Math.max(max,dp[i]);//记录max
        }
        //遍历dp和count获取结果
        int ret = 0;
        for(int i=0;i<n;i++)if(dp[i]==max)ret+=count[i];
        return ret;
    }
}

不同的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //dp[i][j]表示以s[i]和t[j]结尾的s,t的不同序列个数
    //s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1](选择当前s[i]) + dp[i-1][j](不选择当前s[i])
    //s[i] != t[j] 时 dp[i][j] = dp[i-1][j](不选择当前s[i])
    public int numDistinct(String s, String t) {
		int m = s.length();
        int n = t.length();
        if (m < n) return 0;
        int[][] dp = new int[n+1][m+1];
        for(int i=0;i<=m;i++)dp[0][i] = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s.charAt(j-1)==t.charAt(i-1))dp[i][j] = dp[i-1][j-1]+dp[i][j-1];
                else dp[i][j] = dp[i][j-1];
            }
        }
        return dp[n][m];
    }
}

剑指 Offer II 097. 子序列的数目（hard)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
dp[i][j] 表示在 s[i:]的子序列中 t[j:] 出现的个数。(s[i:] 表示 s 从下标 i 到末尾的子字符串，t[j:] 表示 t 从下标 j 到末尾的子字符串)
s的长度为m，t的长度为n

边界情况：
1.当j==n时，t[j:]为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0≤i≤m，有 dp[i][n]=1；
2.当i==m时且j<n，s[i:]为空字符串，t[j:]为非空字符串，由于空字符串不可能是任何非空字符串的子序列，因此对任意 0≤j≤n，有 dp[m][j]=0；

当 i<m 且 j<n 时，考虑 dp[i][j] 的计算：
1.当s[i]==t[j]时，
  1.1 如果 s[i] 和 t[j] 匹配，则考虑 t[j+1:] 作为 s[i+1:] 的子序列，子序列数为 dp[i+1][j+1]；
  1.2 如果 s[i] 和 t[j] 不匹配，则考虑 t[j:] 作为 s[i+1:] 的子序列（前面一个s），子序列数为 dp[i+1][j]。
  因此当 s[i]=t[j] 时，有 dp[i][j]=dp[i+1][j+1]+dp[i+1][j]。

2.当s[i]!=t[j]时，s[i] 不能和 t[j] 匹配，因此只考虑 t[j:] 作为 s[i+1:] 的子序列，子序列数为 dp[i+1][j]。

最终计算得到 dp[0][0] 即为在 s 的子序列中 t 出现的个数。

class Solution {
    //二维dp[i][j]表示
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        //dp[i][j]表示s[i:],t[j:]
        int[][] dp = new int[m+1][n+1];
        //处理边界 t=''(dp[i][n]=1) 和 s=''(i<n时dp[m][i]=0(java数组默认是0无需处理))
        for(int i=0;i<=m;i++)dp[i][n] = 1;
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(s.charAt(i)==t.charAt(j)){
                    dp[i][j] = dp[i+1][j+1]+dp[i+1][j];
                } else dp[i][j]=dp[i+1][j];
            }
        }
        return dp[0][0];
    }
}

1235. 规划兼职工作（hard)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    //dp[i]表示到第i天工作所获得的最大值
    //dp[i]共两种选择
    //1.选择当天工作
    //2.不选择当天工作
    //dp[i] = Math.max(dp[i-1],dp[pre]+profit[i]) pre表示前面最近一次完成的工作结束时间
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n=startTime.length;
        int[][] arr=new int[n][3];
        //构造开始、结束时间、收益的数组
        for(int i=0;i<n;i++){
            arr[i]=new int[]{startTime[i],endTime[i],profit[i]};
        }
        //对结束时间进行排序
        Arrays.sort(arr,(x,y)->x[1]-y[1]);
        int[] dp=new int[n];
        for(int i=0;i<n;i++){
            //查找上一次结束的时间
            int pre= binarySearch(arr,i);
            dp[i]=Math.max(i>0?dp[i-1]:0,(pre>=0?dp[pre]:0)+arr[i][2]);
        }
        return dp[n-1];
    }
    //二分搜索
    int binarySearch(int[][] arr, int i){
        int l=0,r=i-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(arr[mid][1]<=arr[i][0])l=mid;
            else r=mid-1;
        }
        if(l<i&&arr[l][1]<=arr[i][0])return l;
        return -1;
    }
}

64. 最小路径和（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //dp[i][j]表示到达grid[i][j]的最短路径
    //通过条件分析可知每次只能往右和下走所以每次遍历去左边和上边两者的较小值
    //dp[i][j] = grid[i-1][j-1]+Math.min(dp[i-1][j],dp[i][j-1]);
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int 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]=dp[i-1][0]+grid[i][0];
        for(int i=1;i<n;i++)dp[0][i]=dp[0][i-1]+grid[0][i];
        //遍历
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}

圆环回原点问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
 * 输入: 2
 * 输出: 2
 * 解释：有2种方案。分别是0->1->0和0->9->0
 */
//类似爬楼梯
//走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
//dp[i][j]为从0点出发走i步到j点的方案数，则递推式为：dp[i][j]=dp[i-1][(j-1+length)%length]+dp[i-1][j+1+length)%length]
//ps:公式之所以取余是因为j-1或j+1可能会超过圆环0~9的范围
public int rating(int n){
    int length = 10;
    int[][] dp = new int[n][n];
    dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < length; j++) {
            dp[i][j]=dp[i-1][(j-1+length)%length]+dp[i-1][(j+1+length)%length];
        }
    }
    return dp[n-1][0];
}

42. 接雨水（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//首、尾开始遍历取max，ret+=Math.min(leftMax[i],rightMax[i])-height[i];
public int trap(int[] height) {
    int n = height.length;
    if (n==0)return 0;
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1],height[i]);
    }
    rightMax[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i+1],height[i]);
    }
    int ret = 0;
    for (int i = 0; i < n; i++) {
        ret+=Math.min(leftMax[i],rightMax[i])-height[i];
    }
    return ret;
}

1751. 最多可以参加的会议数目 II（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    //dp[i][j] 表示考虑前i个会议，不超过j的最大值
    //dp[i][j] = Math.max(dp[i-1][j],dp[last][j-1]+events[i][2]);
    public int maxValue(int[][] events, int k) {
        int n = events.length;
        int[][] dp = new int[n+1][k+1];
        //按照结束时间排序
        Arrays.sort(events,(x,y)->x[1]-y[1]);
        //遍历
        for(int i=1;i<=n;i++){
            //当前会议
            int[] event = events[i-1];
            int s = event[0], e = event[1],v = event[2];
            // 通过「二分」，找到第 i 件事件之前，与第 i 件事件不冲突的事件
            // 对于当前事件而言，冲突与否，与 j 无关
            int left = 1,right = i - 1;
            //搜索
            while(left<right){
                int mid = (left+right+1)>>1;
                //-1是因为上面进行了+1
                int[] prev= events[mid-1];
                //如果prev[1]<s说明第mid-1的结束时间小于当前会议时间，可选，但是为了保证查找最靠近右边，所以left=mid需要再次逼近右边
                if(prev[1]<s) left = mid;
                //否则mid-1不小于当前会议开始时间，向左移一位
                else right = mid - 1;
            }
            //上次可选的会议
            int last = (right > 0 && events[right - 1][1] < s) ? right : 0;
            for(int j=1;j<=k;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[last][j-1]+v);
            }
        }
        return dp[n][k];
    }
}

1235. 规划兼职工作（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    //dp[i]表示前i个可选的最大值
    //dp[i] = Math.max(dp[i-1],dp[last]+profit)
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] arr = new int[n][3];
        for(int i=0;i<n;i++)arr[i] = new int[]{startTime[i],endTime[i],profit[i]};
        Arrays.sort(arr,(x,y)->x[1]-y[1]);
        int[] dp = new int[n];
        dp[0] = arr[0][2];
        for(int i=1;i<n;i++){
            int[] cur = arr[i];
            int s = cur[0],e = cur[1],p = cur[2];
            //二分搜索之前最近一个可兼职的工作
            int left = 0;
            int right = i - 1;
            dp[i] = arr[i][2];
            while (left < right) {
                int mid = (left + right + 1) >> 1;
                if (arr[mid][1] <= s) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            //如果二分搜索到前面有可兼职的工作
            if (arr[left][1] <= arr[i][0]) {
                dp[i] += dp[left];
            }
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }
        return dp[n-1];
    }
}

279. 完全平方数（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    //dp[i]表示整数i完全平方数的最少数量
    //dp[i] = dp[i-[j*j]]+1  j*j<=i
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i=1;i<=n;i++){
            int min = Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                min = Math.min(min,dp[i-(j*j)]);
            }
            dp[i] = min+1;
        }
        return dp[n];
    }
}

516. 最长回文子序列（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //dp[i][j]表示s[i,j]最长回文串长度
    //dp[i][j]= dp[i+1][j-1]+2 (s[i]==s[j])
    //dp[i][j]= max(dp[i+1][j],dp[i][j-1],dp[i][j]) (s[i]!=s[j])
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n+1][n+1];
        for(int i=n-1;i>=0;i--){
            dp[i][i] = 1;
            for(int j=i+1;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],Math.max(dp[i][j],dp[i][j-1]));
                }
            }
        }
        return dp[0][n-1];
    }
}

357. 统计各位数字都不同的数字个数（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    /**
    * f(0)=1 
    * f(1)=10
    * f(2)=9*9+f(1)
    * f(3)=9*9*8+f(2)
    * f(4)=9*9*8*7+f(3)
    * 左边开始数
    * 首位数不取 0 其他位数可以取 0，下一位比前一位取法少一种，因为不能重复
    * 首位数取 0 时就是 f(n-1)的数量
    */
    public int countNumbersWithUniqueDigits(int n) {
        int[] dp = new int[n+1];
        if(n==0)return 1;
        dp[0] = 1;
        dp[1] = 10;
        for (int i = 2; i < = n; i++) {
            int x = 9;
            for (int j = 9; j > 9-(i-1) ; j--) {
                x = x * j;
            }
            dp[i] = dp[i-1] + x;
        }
        return dp[n];
    }
}

494. 目标和（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    //将数组分为两个子集 (sum−neg)−neg=sum−2⋅neg=target  所以 neg = (sum-target)/2
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num:nums)sum+=num;
        int diff = sum-target;
        //如果diff是负数 或者 不是偶数 说明neg不是整数,无法找到成立的等式
        if(diff < 0 || diff % 2 != 0)return 0;
        //如果以上成立，则可转变为在数组中找若干个数，使其和等于neg
        //定义二维dp[i][j]表示在数组nums的前i个数中选取元素，使其这些元素组成j的方案数。
        //假设数组长度=n,最终答案dp[n][neg]
        //当(nums[i] >j) 此时nums[i]不能选   dp[i][j] = dp[i-1][j] 
        //当(nums[i]<=j) 此时nums[i]不选 dp[i][j] = dp[i-1][j] 选nums[i] 共 dp[i][j] = dp[i-1][j-nums[i]]
        //dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]]
        int n = nums.length;
        int neg = (sum-target)/2;
        int[][] dp = new int[n+1][neg+1];
        //basecase
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=neg;j++){
                dp[i][j] = dp[i-1][j];
                if(nums[i-1]<=j){
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][neg];
    }
}

1014. 最佳观光组合（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //values[i] + values[j] + i - j 变形一下 values[i] + i + values[j] - j (i<j)
    //这样就可以看成是左A[i]+i和右A[j]-j两部分和的最大值。随着遍历数组，我们对两部分和取最大值
    //并且若当前的值—下标对之和比之前更大，我们就更新left部分的值即可。
    public int maxScoreSightseeingPair(int[] values) {
        int n = values.length;
        int leftMax = values[0];
        int ret = Integer.MIN_VALUE;
        for(int i=1;i<n;i++){
            ret = Math.max(leftMax+values[i]-i,ret);
            leftMax = Math.max(leftMax,values[i]+i);
        }
        return ret;
    }
    //bf超时
    // public int maxScoreSightseeingPair(int[] values) {
    //     int n = values.length;
    //     int ret = 0;
    //     for(int i=0;i<n;i++){
    //         for(int j=i+1;j<n;j++){
    //             ret = Math.max(ret,values[i] + values[j] + i - j);
    //         }
    //     }
    //     return ret;
    // }
}

396. 旋转函数（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
    //F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
    //F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
    //F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
    
    //F(0)=0×nums[0]+1×nums[1]+…+(n−1)×nums[n−1]
    //F(1)=1×nums[0]+2×nums[1]+…+0×nums[n−1]=F(0)+numSum−n×nums[n−1]
    //F(2)=2×nums[0]+3×nums[1]+…+1×nums[n−1]=F(1)+numSum−n×nums[n−2]
    //F(k)=F(k−1)+numSum−n×nums[n−k]
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int num:nums)sum+=num;
        int numSum = 0;
        for(int i=0;i<n;i++)numSum+=i*nums[i];
        int ret = numSum;
        int prev = numSum;
        for(int i=1;i<n;i++){
            int cur = prev + sum - n * nums[n-i];
            ret = Math.max(ret,cur);
            prev = cur;
        }
        return ret;
    }
}

467. 环绕字符串中唯一的子字符串（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 给定字符串s="abcdefghijklmnopqrstuvwxyzabcd..."
 *
 * 输入一个字符串 p，输出 p 的子串的数量，满足条件
 * 1，子串同时是 s 的子串
 * 2，重复的子串不计数
 * 3，子串在 p 中是连续的
 * 4，子串在 s 中是连续的
 * 5，子串是非空的
 *
 * 注意：p 不是无限循环字符串的根
 *
 * 举例
 * 输入 p="a"，p 的子串有 "", "a"
 * 满足条件的子串的数量是 1
 *
 * 输入 p="cac"，p的子串有 "", "c", "a", "ca", "ac", "cac"
 * 满足条件的子串的数量是 2，也就是说 "ca"、"ac"、"cac"不是 s 的子串
 *
 * 输入 p="zab"，p的子串有 "", "z", "a", "b", "za", "ab", "zab"
 * 满足条件的子串的数量是 6，也就是说 "z", "a", "b", "za", "ab", "zab" 都是 s 的子串
 */
/**
 * 由于 s 是周期字符串，对于在 s 中的子串，只要知道子串的第一个字符（或最后一个字符）和子串长度，就能确定这个子串。例如子串以 ‘d’ 结尾，长度为 3，那么该子串为 “bcd”。
 * 题目要求不同的子串个数，那么对于两个以同一个字符结尾的子串，长的那个子串必然包含短的那个。例如 “abcd” 和 “bcd” 均以 ‘d’ 结尾，“bcd” 是 “abcd” 的子串。
 * 据此，我们可以定义 dp[α] 表示 p 中以字符 α 结尾且在 s 中的子串的最长长度，知道了最长长度，也就知道了不同的子串的个数。
 * 如何计算 dp[α] 呢？我们可以在遍历 p 时，维护连续递增的子串长度 k。具体来说，遍历到 p[i] 时，如果 p[i] 是 p[i−1] 在字母表中的下一个字母，则将 k 加一，
 * 否则将 k 置为 1，表示重新开始计算连续递增的子串长度。然后，用 k 更新 dp[p[i]] 的最大值。
 * 遍历结束后，p 中以字符 c 结尾且在 s 中的子串有 dp[c] 个。例如 dp[‘d’]=3 表示子串 “bcd”、“cd” 和 “d”。
 *
 * 最后答案为 
 * 
 */
//dp[i]表示i结尾的非空子串的数量
public int findSubstringInWraproundString(String p) {
    int[] dp = new int[26];
    int k = 0;
    for (int i = 0; i < p.length(); ++i) {
        if (i > 0 && (p.charAt(i) - p.charAt(i - 1) + 26) % 26 == 1) { // 字符之差为 1 或 -25
            ++k;
        } else {
            k = 1;
        }
        dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], k);
    }
    return Arrays.stream(dp).sum();
}

926. 将字符串翻转到单调递增（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    //dp[i][0] 表示第i位如果是0结尾最小翻转次数
    //dp[i][1] 表示第i位如果是1结尾最小翻转次数
    //dp[0][0] = dp[0][1] = 0
    //状态转移方程：分为两种情况
    //if(s[i]=='0')
    //dp[i][0] = dp[i-1][0]     //如果当前是s[i]=='0'则dp[i][0]直接取dp[i-1][0]
    //dp[i][1] = min(dp[i-1][0],dp[i-1][1])+1     //因为当前是s[i]=='0',且dp[i][1]表示第i位如果是1结尾最小翻转次数,那么要变为'1'必须+1,则dp[i][1]可取的情况是 min(dp[i-1][0],dp[i-1][1])+1 
    //if(s[i]=='1')
    //dp[i][0] = dp[i-1][0] + 1;      //如果当前是s[i]=='1'则dp[i][0]直接取dp[i-1][0]+1（把1变成0）
    //dp[i][1] = min(dp[i-1][0],dp[i-1][1])       //因为当前是s[i]=='1',此时不管是s[i-1]是'0'还是'1'都不需要改动,只需取其两者的最小值即可
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[][] dp = new int[n+1][2];
        for(int i=1;i<=n;i++){
            if(s.charAt(i-1)=='0'){
                dp[i][0] = dp[i-1][0];
                dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1])+1;
            }
            if(s.charAt(i-1)=='1'){
                dp[i][0] = dp[i-1][0] + 1;
                dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]);
            }
        }
        return Math.min(dp[n][0],dp[n][1]);
    }
}

1289. 下降路径最小和 II（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //dp[i][j] = for j in n Math.min(dp[i-1]+grid[i][j],) j!=i
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++)dp[0][i] = grid[0][i];
        for(int i=1;i<n;i++){
            for(int j=0;j<n;j++){
                int v = 1000000;
                for(int k=0;k<n;k++){
                    if(k==j)continue;
                    v = Math.min(v,dp[i-1][k]+grid[i][j]);
                }
                dp[i][j] = v;
            }
        }
        int ret = dp[n-1][0];
        for(int i=0;i<n;i++)ret = Math.min(dp[n-1][i],ret);
        return ret;
    }
}

相关资料

基础算法 > 刷题记录
#动态规划
算法学习-动态规划
https://mikeygithub.github.io/2020/09/09/yuque/算法学习-动态规划/
作者
Mikey
发布于
2020年9月9日
许可协议