力扣刷题：动态规划篇

r囧r小猫 2022-10-16 09:40 258阅读 0赞

### 目录 ###

*  10. 正则表达式匹配
 *   *  题目介绍
     *  题目实现
 *  32. 最长有效括号
 *   *  题目介绍
     *  题目实现
 *  322. 零钱兑换
 *   *  题目介绍
     *  题目实现
 *  343. 整数拆分
 *   *  题目介绍
     *   *   *  \[剑指 Offer 14- I. 剪绳子\](https://leetcode-cn.com/problems/jian-sheng-zi-lcof/)
     *  题目实现
 *  42. 接雨水
 *   *  题目介绍
     *  题目实现
 *  44. 通配符匹配
 *   *  题目介绍
     *  题目实现
 *  5. 最长回文子串
 *   *  题目介绍
     *  题目实现
 *  518. 零钱兑换 II
 *   *  题目介绍
     *  题目实现
 *  53. 最大子序和
 *   *  题目介绍
     *  题目实现
 *  55. 跳跃游戏
 *   *  题目介绍
     *  题目实现
 *  63. 不同路径 II
 *   *  题目介绍
     *   *   *  \[62. 不同路径\](https://leetcode-cn.com/problems/unique-paths/)
     *  题目实现
 *  70. 爬楼梯
 *   *  题目介绍
     *  题目实现
 *  72. 编辑距离
 *   *  题目介绍
     *  题目实现
 *  专题 000. 买卖股票的所有问题
 *   *  \[121. 买卖股票的最佳时机\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
     *  \[122. 买卖股票的最佳时机 II\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)
     *  \[123. 买卖股票的最佳时机 III\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)
     *  \[188. 买卖股票的最佳时机 IV\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)
     *  \[714. 买卖股票的最佳时机含手续费\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
     *  \[309. 最佳买卖股票时机含冷冻期\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)
 *  剑指 Offer 14- I. 剪绳子
 *   *  题目介绍
     *   *   *  \[343. 整数拆分\](https://leetcode-cn.com/problems/integer-break/)
     *  题目实现
 *  剑指 Offer 14- II. 剪绳子 II
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 47. 礼物的最大价值
 *   *  题目介绍
     *   *   *  \[64. 最小路径和\](https://leetcode-cn.com/problems/minimum-path-sum/)
             *  \[62. 不同路径\](https://leetcode-cn.com/problems/unique-paths/)
     *  题目实现
 *  面试题 08.11. 硬币
 *   *  题目介绍
     *  题目实现

--------------------

# 10. 正则表达式匹配 #

## 题目介绍 ##

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘\*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符  
‘\*’ 匹配零个或多个前面的那一个元素  
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

**示例 1：**

输入：s = "aa" p = "a"
    输出：false
    解释："a" 无法匹配 "aa" 整个字符串。

**示例 2：**

输入：s = "aa" p = "a*"
    输出：true
    解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

**示例 3：**

输入：s = "ab" p = ".*"
    输出：true
    解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

**示例 4：**

输入：s = "aab" p = "c*a*b"
    输出：true
    解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

**示例 5：**

输入：s = "mississippi" p = "mis*is*p*."
    输出：false

**提示：**

*  0 <= s.length <= 20
 *  0 <= p.length <= 30
 *  s 可能为空，且只包含从 a-z 的小写字母。
 *  p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。
 *  保证每次出现字符 \* 时，前面都匹配到有效的字符

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/regular-expression-matching  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![05db8bf07ac0abf2e64490b0fe46c5bc.png][]

![897464d6e839ab0e3530d0da1ee85873.png][]

class Solution { 
        public boolean isMatch(String ss, String pp) { 
            int m = ss.length(), n = pp.length();
            char[] s = ss.toCharArray(), p = pp.toCharArray();
            boolean[][] dp = new boolean[m + 1][n + 1];
            //初始化值
            dp[0][0] = true;
            for (int j = 0; j < n; j++) { 
                if (p[j] == '*') { 
                    dp[0][j + 1] = dp[0][j - 1];
                }
            }
            //动态规划
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (p[j] == '*') { 
                        if (p[j - 1] == '.') { 
                            if (dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1]) { 
                                dp[i + 1][j + 1] = true;
                            }
                        } else { 
                            if (dp[i + 1][j - 1] || dp[i + 1][j] || (s[i] == p[j - 1] && dp[i][j + 1])) { 
                                dp[i + 1][j + 1] = true;
                            }
                        }
                    } else if (p[j] == '.' || s[i] == p[j]) { 
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                }
            }
            return dp[m][n];
        }
    }

# 32. 最长有效括号 #

## 题目介绍 ##

给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

**示例 1：**

输入：s = "(()"
    输出：2
    解释：最长有效括号子串是 "()"

**示例 2：**

输入：s = ")()())"
    输出：4
    解释：最长有效括号子串是 "()()"

**示例 3：**

输入：s = ""
    输出：0

**提示：**

*  0 <= s.length <= 3 \* 104
 *  `s[i]` 为 `'('` 或 `')'`

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-valid-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![82b3f7d81c91d7c2e721ec7d5fd68bbb.png][]

class Solution { 
        public int longestValidParentheses(String s) { 
            char[] chars = s.toCharArray();
            int[] dp = new int[chars.length];
            int max = 0;
            for (int i = 1; i < chars.length; i++) { 
                if (chars[i] == ')') { 
                    if (chars[i - 1] == '(') { 
                        dp[i] = 2;
                        if (i - 2 >= 0) { 
                            dp[i] = dp[i] + dp[i - 2];
                        }
                    } else { 
                        if ((i - dp[i - 1] - 1) >= 0 && chars[i - dp[i - 1] - 1] == '(') { 
                            dp[i] = dp[i - 1] + 2;
                            if ((i - dp[i - 1] - 2) >= 0) { 
                                dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                            }
                        }
                    }
                }
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    }

# 322. 零钱兑换 #

## 题目介绍 ##

给定不同面额的硬币 `coins` 和一个总金额 `amount`。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 `-1`。你可以认为每种硬币的数量是无限的。

**示例 1：**

输入：coins = [1, 2, 5], amount = 11
    输出：3 
    解释：11 = 5 + 5 + 1

**示例 2：**

输入：coins = [2], amount = 3
    输出：-1

**示例 3：**

输入：coins = [1], amount = 0
    输出：0

**示例 4：**

输入：coins = [1], amount = 1
    输出：1

**示例 5：**

输入：coins = [1], amount = 2
    输出：2

**提示：**

*  1 <= coins.length <= 12
 *  1 <= coins\[i\] <= 231 \- 1
 *  0 <= amount <= 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/coin-change  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

假设题目输入：coins = \[1, 2, 5\], amount = 11

我们采用自下而上的方式进行思考。定义 `F(i)` 为组成金额 `i` 所需最少的硬币数量，当 `i==0` 时无法用硬币组成，为 `0` 。

![7103c15923783092a6ee4c93ada79a74.png][]

除下标 0 以外，其他所有下标（金额）所对应的值，都为 `amount + 1`。

![7103c15923783092a6ee4c93ada79a74.png][]

当下标（金额）为1的时候，此时有三种面值的金币可以选择，下标（金额）1减去这三种面值的大小，分别得到0、-1、-4，负数不在考虑范围，选择其中最小的值，也就是0，其实当金额等于0的时候，组成0所需的最少金币就是0，因为F(1 - 1)减去了一个面值为1的金币，所以我们只需要让组成0所需的最少金币 + 1（面值为1，因为你减去的是1，这里的1代表1个金币，实际上，这个面值可以是1、可以是2、可以是5，看哪个能减去并且组成的金币数是最小的，那这个1就代表哪个面值，虽然1是不变的，但是1所代表的面值是一直变化的）

![4544660dc2536487db0156bb85b4c3f4.png][]

当下标（金额）为2的时候，此时有三种面值的金币可以选择，下标（金额）2减去这三种面值的大小，分别得到1、0、-3，负数不在考虑范围，选择其中最小的值，也就是0，其实当金额等于0的时候，组成0所需的最少金币就是0，因为F(2 - 2)减去了一个面值为2的金币，所以我们只需要让组成0所需的最少金币 + 1（面值为2，因为你减去的是2，这里的1代表1个金币，实际上，这个面值可以是1、可以是2、可以是5，看哪个能减去并且组成的金币数是最小的，那这个1就代表哪个面值，虽然1是不变的，但是1所代表的面值是一直变化的）

![92a81ee7f5521150c5a2acf9deb8c775.png][]

当下标（金额）为3的时候，此时有三种面值的金币可以选择，下标（金额）3减去这三种面值的大小，分别得到2、1、-2，负数不在考虑范围，选择其中最小的值，也就是1，其实当金额等于1的时候，组成1所需的最少金币就是1，因为F(3 - 2)减去了一个面值为2的金币，所以我们只需要让组成1所需的最少金币 + 1（面值为2，因为你减去的是2，这里的1代表1个金币，实际上，这个面值可以是1、可以是2、可以是5，看哪个能减去并且组成的金币数是最小的，那这个1就代表哪个面值，虽然1是不变的，但是1所代表的面值是一直变化的）

![a6e0d3e19daa2e13ebef6a2e80cf678a.png][]

按照上述规律进行依次向后计算…

当下标（金额）为11的时候，此时有三种面值的金币可以选择，下标（金额）3减去这三种面值的大小，分别得到10、9、6，选择其中最小的值，也就是6，其实当金额等于6的时候，组成6所需的最少金币就是2，因为F(11 - 5)减去了一个面值为5的金币，所以我们只需要让组成6所需的最少金币 + 1（面值为5，因为你减去的是5，这里的1代表1个金币，实际上，这个面值可以是1、可以是2、可以是5，看哪个能减去并且组成的金币数是最小的，那这个1就代表哪个面值，虽然1是不变的，但是1所代表的面值是一直变化的）

![74783774d3499f814e3c600127c8204b.png][]

这里给出比较完整的变化过程参考：

![2c595d40f724873898a915cfd90e17ce.png][]

最后返回的时候，我们怎么保证，如果没有任何一种硬币组合能组成总金额，返回 `-1`。只需要进行一个判断即可。

dp[amount] == maxAmount ? -1 : dp[amount]

最终完整的代码：

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

# 343. 整数拆分 #

## 题目介绍 ##

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m-1\] 。请问 `k[0]*k[1]*...*k[m-1]` 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

**示例 1：**

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2：**

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

**提示：**

*  2 <= n <= 58

**相同题目：**

*  #### [剑指 Offer 14- I. 剪绳子][Offer 14- I.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/integer-break/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![ad2718fb6b96ee51b4fd10deb112e87b.png][]

class Solution { 
        public int cuttingRope(int n) { 
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i < n + 1; i++) { 
                for (int j = 2; j < i; j++) { 
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                }
            }
            return dp[n];
        }
    }

# 42. 接雨水 #

## 题目介绍 ##

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

**示例 1：**

![a4245551f0fa20e045683836941ad3a2.png][]

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

**示例 2：**

输入：height = [4,2,0,3,2,5]
    输出：9

**提示：**

*  n == height.length
 *  0 <= n <= 3 \* 104
 *  0 <= height\[i\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/trapping-rain-water  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![ca2b4943cc2ad2eb9712b1bcfca0577c.png][]

class Solution { 
        public int trap(int[] height) { 
            int n = height.length;
            if (n == 0) return 0;
    
            int[] lm = new int[n];
            lm[0] = height[0];
            for (int i = 1; i < n; i++) { 
                lm[i] = Math.max(lm[i - 1], height[i]);
            }
    
            int[] rm = new int[n];
            rm[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; i--) { 
                rm[i] = Math.max(height[i], rm[i + 1]);
            }
    
            int sum = 0;
            for (int i = 0; i < n; i++) { 
                sum += Math.min(lm[i], rm[i]) - height[i];
            }
            return sum;
        }
    }

# 44. 通配符匹配 #

## 题目介绍 ##

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘\*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。  
‘\*’ 可以匹配任意字符串（包括空字符串）。  
两个字符串完全匹配才算匹配成功。

说明:

*  s 可能为空，且只包含从 a-z 的小写字母。
 *  p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 \*。

**示例 1：**

输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。

**示例 2：**

输入:
    s = "aa"
    p = "*"
    输出: true
    解释: '*' 可以匹配任意字符串。

**示例 3：**

输入:
    s = "cb"
    p = "?a"
    输出: false
    解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

**示例 4：**

输入:
    s = "adceb"
    p = "*a*b"
    输出: true
    解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce"。

**示例 5：**

输入:
    s = "acdcb"
    p = "a*c?b"
    输出: false

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/wildcard-matching  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![7b985fcd76b53db0ae4a7328a2c3b7a5.png][]

![661ac955a1700eda718ce56ec2d8111f.png][]

class Solution { 
        public boolean isMatch(String ss, String pp) { 
            int m = ss.length(), n = pp.length();
            char[] s = ss.toCharArray(), p = pp.toCharArray();
            boolean[][] dp = new boolean[m + 1][n + 1];
            //初始化值
            dp[0][0] = true;
            for (int j = 0; j < n; j++) { 
                if (p[j] == '*') { 
                    dp[0][j + 1] = true;
                } else { 
                    break;
                }
            }
            //动态规划
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (p[j] == '*') { 
                        dp[i + 1][j + 1] = dp[i + 1][j] || dp[i][j + 1];
                    } else if (p[j] == '?' || s[i] == p[j]) { 
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                }
            }
            return dp[m][n];
        }
    }

# 5. 最长回文子串 #

## 题目介绍 ##

给你一个字符串 `s`，找到 `s` 中最长的回文子串。

**示例 1：**

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

**示例 2：**

输入：s = "cbbd"
    输出："bb"

**示例 3：**

输入：s = "a"
    输出："a"

**示例 4：**

输入：s = "ac"
    输出："a"

**提示：**

*  1 <= s.length <= 1000
 *  s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-substring  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![80374f1290249cad33045a6e18b65b5c.png][]

假设字符串s（“babad”）的长度为n。

`dp`是大小为 n \* n 的二维数组，`dp[i][j]`表示`s[i][j]`是否是回文串，如果是存储true，不过不是存储false。

如何求出`dp[i][j]`的值呢？

这里分为两种情况：

![30e9c5363a07a4f1f4ec6bd6a78dcf9e.png][]

class Solution { 
        public String longestPalindrome(String s) { 
            int len = s.length(), max = 1, pos = 0;
            char[] c = s.toCharArray();
            boolean[][] dp = new boolean[len][len];
            for (int i = len - 1; i >= 0; i--) { 
                for (int j = i; j < len; j++) { 
                    int size = j - i + 1;
                    dp[i][j] = (size <= 2 || dp[i + 1][j - 1]) && c[i] == c[j];
                    if (dp[i][j] && size > max) { 
                        max = size;
                        pos = i;
                    }
                }
            }
            return new String(c, pos, max);
        }
    }

# 518. 零钱兑换 II #

## 题目介绍 ##

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

**示例 1：**

输入: amount = 5, coins = [1, 2, 5]
    输出: 4
    解释: 有四种方式可以凑成总金额:
    5=5
    5=2+2+1
    5=2+1+1+1
    5=1+1+1+1+1

**示例 2：**

输入: amount = 3, coins = [2]
    输出: 0
    解释: 只用面额2的硬币不能凑成总金额3。

**示例 3：**

输入: amount = 10, coins = [10] 
    输出: 1

**注意：**

你可以假设：

*  0 <= amount (总金额) <= 5000
 *  1 <= coin (硬币面额) <= 5000
 *  硬币种类不超过 500 种
 *  结果符合 32 位符号整数

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/coin-change-2  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

让我们举一个例子：amount = 11，可用面值有 2 美分，5 美分和 10 美分。 请注意，数量是无限的。

![2180f6bbcbb7af8defe3cd8b9c7e54eb.png][]

**基本情况：**

*  如果`amount (总金额) = 0`，那么只有一个组合情况：`0`，初始化应该赋值为 `1`。
 *  如果`amount (总金额) > 0`，则组合情况为 `0`。

![378c84ffe73f0d8a3bdef5523b5ab0d0.png][]

**二美分：**

*  让我们做进一步考虑：`2` 美分。
 *  很明显，这里可能会有 `1` 种或 `0` 种组合。偶数金额为 `1` 种，奇数金额为 `0` 种。
 *  首先，所有金额均小于 `2` 美分不会受到 `2` 美分的影响。 因此对于 `amount = 0` 和 `amount = 1` 的结果没有变化。
 *  从 `amount = 2` 开始，可以使用 `2` 美分进行组合。
 *  我们使用 `2` 美分来组合 `amount = 2`，则金额 `2` 美分的组合数等于 `amount = 0` 的组合数量，即 `1`。
 *  同理 `amount = 3` 的组合数量等于 `amount = 1` 的组合数量，即 `0`。
 *  我们可以推到出 `DP` 公式为 `dp[x] = dp[x] + dp[x - coin]`，其中 coin = `2` 美分，是当前添加的价值。

![19104017574bf8b41b3517850b3bbf7f.png][]

**二美分+五美分：**

*  我们增加 `5` 美分的情况，公式是一样的。

![de60eaa294d97aa1d551e4824d508bfa.png][]

**二美分+五美分+十美分：**

*  对于 `10` 美分也是一样的。

![a58ddaaf580a641e508cddc2bbbb746c.png][]

class Solution { 
        public int change(int amount, int[] coins) { 
                int maxAmount = amount + 1;
                int[] dp = new int[maxAmount];
                dp[0] = 1;
                for (int coin : coins) { 
                    for (int x = 0; x < maxAmount; x++) { 
                        if (x >= coin) { 
                            dp[x] = dp[x] + dp[x - coin];
                        }
                    }
                }
                return dp[amount];
        }
    }

进一步优化：

class Solution { 
        public int change(int amount, int[] coins) { 
            int maxAmount = amount + 1;
            int[] dp = new int[maxAmount];
            dp[0] = 1;
            for (int coin : coins) { 
                for (int x = coin; x < maxAmount; x++) { 
                    dp[x] = dp[x] + dp[x - coin];
                }
            }
            return dp[amount];
        }
    }

# 53. 最大子序和 #

## 题目介绍 ##

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

**示例 1：**

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

**示例 2：**

输入：nums = [1]
    输出：1

**示例 3：**

输入：nums = [0]
    输出：0

**示例 4：**

输入：nums = [-1]
    输出：-1

**示例 5：**

输入：nums = [-100000]
    输出：-100000

**提示：**

*  1 <= nums.length <= 3 \* 104
 *  \-105 <= nums\[i\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-subarray  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 `sum`，结果为 `ans` 。

*  如果 `sum > 0`，则说明 `sum` 对结果有增益效果，则 `sum` 保留并加上当前遍历数字。
 *  如果 `sum <= 0`，则说明 `sum` 对结果无增益效果，需要舍弃，则 `sum` 直接更新为当前遍历数字。

每次比较 `sum` 和 `ans` 的大小，将最大值置为 `ans`，遍历结束返回结果。

class Solution { 
        public int answer(int[] nums) { 
            if (nums == null || nums.length == 0) return 0;
            int ans = Integer.MIN_VALUE, sum = 0;
            for (int num : nums) { 
                //如果sum + num > num，则说明sum对结果有增益效果，则sum保留并加上当前遍历数字。
                if (sum + num > num) { 
                    sum += num;
                }
                //否则，则说明sum对结果无增益效果，需要舍弃后重新开始，则sum直接更新为当前遍历数字。
                else { 
                    sum = num;
                }
                //每次比较sum和ans的大小，将最大值置为ans，遍历结束返回结果。
                ans = Math.max(ans, sum);
            }
            return ans;
        }
    }

# 55. 跳跃游戏 #

## 题目介绍 ##

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

**示例 1：**

输入：nums = [2,3,1,1,4]
    输出：true
    解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

**示例 2：**

输入：nums = [3,2,1,0,4]
    输出：false
    解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

**提示：**

*  1 <= nums.length <= 3 \* 104
 *  0 <= nums\[i\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/jump-game  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![92a6a288c436288a3c08568e16a64d0f.png][]

![d1e35a8c3de25de9b586f466d9b4dca0.png][]

class Solution { 
        public boolean canJump(int[] nums) { 
            int n = nums.length;
            boolean[] dp = new boolean[n];
            dp[0] = true;
            for (int j = 1; j < n; j++) { 
                for (int i = 0; i < j; i++) { 
                    if (dp[i] && i + nums[i] >= j) { 
                        dp[j] = true;
                        break;
                    }
                }
            }
            return dp[n - 1];
        }
    }

# 63. 不同路径 II #

## 题目介绍 ##

一个机器人位于一个 `m x n` 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

![0bd29b746bd31c42319ab088dbaa568e.png][]

网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。

**示例 1：**

![0d1a7b2ce40ac50fe8a3ea877106cc29.png][]

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    输出：2
    解释：
    3x3 网格的正中间有一个障碍物。
    从左上角到右下角一共有 2 条不同的路径：
    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右

**示例 2：**

![ad6c49fe794fc95e0b0988e72e21fbad.png][]

输入：obstacleGrid = [[0,1],[0,0]]
    输出：1

**提示：**

*  m == obstacleGrid.length
 *  n == obstacleGrid\[i\].length
 *  1 <= m, n <= 100
 *  `obstacleGrid[i][j]` 为 0 或 1

**相似题目：**

*  #### [62. 不同路径][62.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/unique-paths-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int uniquePathsWithObstacles(int[][] obstacleGrid) { 
            // 创建 dp 数组
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            // 初始化第一列
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) { 
                dp[i][0] = 1;
            }
            // 初始化第一行
            for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) { 
                dp[0][i] = 1;
            }
            // 动态规划核心
            for (int i = 1; i < m; i++) { 
                for (int j = 1; j < n; j++) { 
                    if (obstacleGrid[i][j] == 0) { 
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            // 返回最后元素
            return dp[m - 1][n - 1];
        }
    }

# 70. 爬楼梯 #

## 题目介绍 ##

假设你正在爬楼梯。需要 `n` 阶你才能到达楼顶。

每次你可以爬 `1` 或 `2` 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 `n` 是一个正整数。

**示例 1：**

输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶

**示例 2：**

输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/climbing-stairs  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

本问题其实常规解法可以分成多个子问题，爬第 `n` 阶楼梯的方法数量，等于以下 `2` 部分之和：

*  爬上 `n-1` 阶楼梯的方法数量。因为再爬 `1` 阶就能到第 `n` 阶
 *  爬上 `n-2` 阶楼梯的方法数量，因为再爬 `2` 阶就能到第 `n` 阶

所以我们得到公式 `dp[n] = dp[n-1] + dp[n-2]`，同时需要初始化 `dp[0] = dp[1] = 1`

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

# 72. 编辑距离 #

## 题目介绍 ##

给你两个单词 `word1` 和 `word2`，请你计算出将 `word1` 转换成 `word2` 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

*  插入一个字符
 *  删除一个字符
 *  替换一个字符

**示例 1：**

输入：word1 = "horse", word2 = "ros"
    输出：3
    解释：
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')

**示例 2：**

输入：word1 = "intention", word2 = "execution"
    输出：5
    解释：
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')

**提示：**

*  0 <= word1.length, word2.length <= 500
 *  word1 和 word2 由小写英文字母组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/edit-distance  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![b17c88ab27b66ef737de45ee520c5398.png][]

假设字符串1（“mice”）为s1，它的长度为n1；字符串2（“arise”）为s2，它的长度为n2。

`dp`是一个大小为（n1+1）\*（n2+1）的二维数组，`dp[i][j]`代表`s1[i][0]`转换为`s2[0][j]`所需要的最少次数。

显然，`dp[n1][n2]`位置处的数值，就是我们最终所要求得的字符串1（“mice”）转为字符串2（“arise”）所需要的最少操作数。

其中，`dp[0][0]`位置代表的是空字符串（“”）。

因此，第一列除了`dp[0][0]`其余元素值应该初始化为对应的下标。第一行除了`dp[0][0]`其余元素值应该初始化为对应的下标。

无论是第一列还是第一行，`s1[i][0]` 或 `s2[0][j]`所组成的字符串转化为空字符串（“”）时，所需要的最少次数就是其对应的下标。

![7cd8f52c160b574a435cb1fa2a9ead0c.png][]

![f49380558ef7d323dee90bc3c26b4f94.png][]

如何求出其他位置的`dp[i][j]`呢？

在这里我们分为四种情况：  
![1cc34ca0850f1ca3761370cd546ea45f.png][]

![37a19d5d1bd6fa2cab240076333a9716.png][]

class Solution { 
        public int minDistance(String word1, String word2) { 
            // 临界值检查
            int n1 = word1.length();
            int n2 = word2.length();
            if (n1 * n2 == 0) return n1 + n2;
            // 转字符数组
            char[] s1 = word1.toCharArray();
            char[] s2 = word2.toCharArray();
            // 建立dp数组
            int[][] dp = new int[n1 + 1][n2 + 1];
            // 初始第一列
            for (int i = 0; i < n1 + 1; i++) { 
                dp[i][0] = i;
            }
            // 初始第一行
            for (int j = 1; j < n2 + 1; j++) { 
                dp[0][j] = j;
            }
            // 计算其他值
            for (int i = 1; i < n1 + 1; i++) { 
                for (int j = 1; j < n2 + 1; j++) { 
                    int top = dp[i - 1][j] + 1;
                    int left = dp[i][j - 1] + 1;
                    int leftTop = dp[i - 1][j - 1];
                    if (s1[i - 1] != s2[j - 1]) leftTop++;
                    dp[i][j] = Math.min(Math.min(top, left), leftTop);
                }
            }
            // 返回结果值
            return dp[n1][n2];
        }
    }

# 专题 000. 买卖股票的所有问题 #

## [121. 买卖股票的最佳时机][121.] ##

想通这一招，搞定所有股票买卖问题，包括买卖股票的最佳时机（1,2,3,4）、含冷冻期、含手续费。

**我们要跳出固有的思维模式，并不是要考虑买还是卖，而是要最大化手里持有的钱。**

**买股票手里的钱减少，卖股票手里的钱增加，无论什么时刻，我们要保证手里的钱最多。**

**我们这一次买还是卖只跟上一次我们卖还是买的状态有关。**

我们解题需要使用动态规划，既然用了动态规划，肯定是要用 **空间换时间** 。

我们先看下执行状态，这是一个买入和卖出的过程，而且能交易一次即只能买卖一次，所以 **买入** 之后，状态可以转换到 **卖出** ，但是 **卖出** 之后就不能再 **买入** 了，因为只能 **买卖一次** 。

![f48dc210de290eb35f28a3fbebd8a762.png][]

我们需要用开辟额外的空间，来不断更新买入和卖出的最大收益。

![b3e654c102f3e0fa2c012c614a6d1a6d.png][]

我们先看一个最简单的例子，假设只数组长度是 **1** ，即只有一天。

这时候不管股价是多少，我的收益都是0，为什么呢？

因为必须要先买后卖，只有一天的情况下无法卖出，所以卖出的收益是0。

股价是7美元，也就是花了7美元买进这个股票，那么对应到第一天买入的最大收益就是-7美元。两者一合计当然是坐地不动更划算。

![84397e6ef2335ceb53949918034ed2bd.png][]

我们再来看一个复杂点的，假设有三天。这里卖出数组记录了每次卖出的最大收益，数组下标i即对应第i天的最大收益。

买入数组记录了每次买入的最大收益，数组下标i即对应第i天的最大收益，第一天的时候还是老样子，卖出是0，买入是-7。

第二天卖出的最大利润仍然是0。

卖出的收益是：第一天买入的值-7，加上第二天股票价格，也就是第一天我花7美元买入(买入对应收益就是-7)，第二天1美元卖出，所以第二天的卖出收益就是-6美元。这当时是亏本了，于是继续不动。

买入的收益是：记录当天买入的最大收益，因为买入都是负的，所以最大收益就是找一个价格最低的，即前一天买入的最大收益vs第二天的股价，第一天花了7美元买入的，第二天股票跌到1美元，当然是买第二天的。

![d8933b95d0993ddf22a699384702668a.png][]

第三天卖出的利润就变了。

卖出收益是：第二天买入的值-1，加上第三天的股票价格，也就是前一天买入的最大收益 -1加上第三天的股票价格5，于是第三天买入的收益就变成了4。

买入的收益是：第二天买入的值-1 vs 第三天买入的股价-5，选择不动。

![6f9e7fce8802e3792dba722b532733ef.png][]

我们先看当前问题的代码，其中buy和sell都代表操作之后手里的钱。如果只买一次，那么上一个状态一定是0。

class Solution { 
        public int maxProfit(int[] prices) { 
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            for (int price : prices) { 
                buy = Math.max(buy, 0 - price);
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }
    }

## [122. 买卖股票的最佳时机 II][122. _ II] ##

这个问题和上一个问题唯一的不同点在于我们是买一次还是买无穷多次，而代码就只有 **0-p** 和 **sell-p** 的区别。  
因为如果买无穷多次，就需要上一次卖完的状态。如果只买一次，那么上一个状态一定是0。

class Solution { 
        public int maxProfit(int[] prices) { 
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            for (int price : prices) { 
                buy = Math.max(buy, sell - price);
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }
    }

## [123. 买卖股票的最佳时机 III][123. _ III] ##

第三题只允许最多买两次，那么就有四个状态，第一次买，第一次卖，第二次买，第二次卖。

还是那句话，无论什么状态，我们要保证手里的钱最多。

class Solution { 
        public int maxProfit(int[] prices) { 
            int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
            int sell1 = 0, sell2 = 0;
            for (int price : prices) { 
                buy1 = Math.max(buy1, 0 - price);
                sell1 = Math.max(sell1, buy1 + price);
                buy2 = Math.max(buy2, sell1 - price);
                sell2 = Math.max(sell2, buy2 + price);
            }
            return sell2;
        }
    }

## [188. 买卖股票的最佳时机 IV][188. _ IV] ##

到了第四题，相信大家已经要懂了，第三题最多两次我们有2x2个状态，那么k次我们就需要kx2个状态。

那么我们并不需要像第三题那样真的列kx2个参数，我们只需要两个数组就可以了。

class Solution { 
        public int maxProfit(int k, int[] prices) { 
            // 加入下边这句话可以优化速度，提升性能
            // k = Math.min(k, prices.length / 2);
            int[] buy = new int[k + 1];
            Arrays.fill(buy, Integer.MIN_VALUE);
            int[] sell = new int[k + 1];
            for (int price : prices) { 
                for (int i = 1; i < k + 1; i++) { 
                    buy[i] = Math.max(buy[i], sell[i - 1] - price);
                    sell[i] = Math.max(sell[i], buy[i] + price);
                }
            }
            return sell[k];
        }
    }

## [714. 买卖股票的最佳时机含手续费][714.] ##

这道题只是第二题的变形，每次买卖需要手续费，那么我们买的时候减掉手续费就行了。

class Solution { 
        public int maxProfit(int[] prices, int fee) { 
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            for (int price : prices) { 
                buy = Math.max(buy, sell - price - fee);
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }
    }

## [309. 最佳买卖股票时机含冷冻期][309.] ##

这道题只是第二题的变形，卖完要隔一天才能买，那么就多记录上一次卖的状态即可。

class Solution { 
        public int maxProfit(int[] prices) { 
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            int sellPre = 0;
            for (int price : prices) { 
                buy = Math.max(buy, sellPre - price);
                sellPre = sell;
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }
    }

# 剑指 Offer 14- I. 剪绳子 #

## 题目介绍 ##

**示例 1：**

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2：**

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

**提示：**

*  2 <= n <= 58

**相同题目：**

*  #### [343. 整数拆分][343.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![ad2718fb6b96ee51b4fd10deb112e87b.png][]

# 剑指 Offer 14- II. 剪绳子 II #

## 题目介绍 ##

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\] 。请问 `k[0]*k[1]*...*k[m - 1]` 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

**示例 1：**

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2：**

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

**提示：**

*  2 <= n <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

import java.math.BigInteger;
    import java.util.Arrays;
    
    class Solution { 
        public int cuttingRope(int n) { 
            BigInteger[] dp = new BigInteger[n + 1];
            Arrays.fill(dp, BigInteger.valueOf(0));
            dp[2] = BigInteger.valueOf(1);
            for (int i = 3; i < n + 1; i++) { 
                for (int j = 2; j < i; j++) { 
                    dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
                }
            }
            return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
        }
    }

# 剑指 Offer 47. 礼物的最大价值 #

## 题目介绍 ##

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

**示例 1：**

输入: 
    [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

**提示：**

*  0 < grid.length <= 200
 *  0 < grid\[0\].length <= 200

**相似题目：**

*  #### [64. 最小路径和][64.] ####
 *  #### [62. 不同路径][62.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

从棋盘的左上角开始拿格子里的礼物，并每次 **向右** 或者 **向下** 移动一格、直到到达棋盘的右下角。

根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。

![c605992c817a45901e5e9383c3988dde.png][]

设 `f(i, j)` 为从棋盘左上角走至单元格 `(i ,j)` 的礼物最大累计价值，易得到以下递推关系：`f(i,j)` 等于 `f(i,j-1)` 和 `f(i-1,j)` 中的较大值加上当前单元格礼物价值 `grid(i,j)`。

![9f6d843a389b5a2bc0c48348e0c7b141.png][]

因此，可用动态规划解决此问题，以上公式便为转移方程。

![19c3e4e95a280e03605f60d883697d6c.png][]

由于 `dp[i][j]` 只与 `dp[i-1][j]` , `dp[i][j-1]`, `grid[i][j]` 有关系，因此可以将原矩阵 `grid` 用作 `dp` 矩阵，即直接在 `grid` 上修改即可。应用此方法可省去 `dp` 矩阵使用的额外空间，因此空间复杂度从 `O(MN)` 降至 `O(1)` 。

class Solution { 
        public int maxValue(int[][] grid) { 
            // 对临界值的判断
            int rows = grid.length;
            int cols = grid[0].length;
            if (grid == null || rows == 0 || cols == 0) return 0;
            // 初始化第一列
            for (int i = 1; i < rows; i++) { 
                grid[i][0] = grid[i - 1][0] + grid[i][0];
            }
            // 初始化第一行
            for (int i = 1; i < cols; i++) { 
                grid[0][i] = grid[0][i - 1] + grid[0][i];
            }
            // 动态规划核心
            for (int i = 1; i < rows; i++) { 
                for (int j = 1; j < cols; j++) { 
                    grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
            // 返回最后元素
            return grid[rows - 1][cols - 1];
        }
    }

# 面试题 08.11. 硬币 #

## 题目介绍 ##

硬币。给定数量不限的硬币，币值为`25`分、`10`分、`5`分和`1`分，编写代码计算`n`分有几种表示法。

注意：结果可能会很大，你需要将结果模上`1000000007`。

**示例 1：**

输入: n = 5
     输出：2
     解释: 有两种方式可以凑成总金额:
    5=5
    5=1+1+1+1+1

**示例 2：**

输入: n = 10
     输出：4
     解释: 有四种方式可以凑成总金额:
    10=10
    10=5+5
    10=5+1+1+1+1+1
    10=1+1+1+1+1+1+1+1+1+1

**说明：**

*  0 <= n (总金额) <= 1000000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/coin-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

让我们举一个例子：amount = 11，可用面值有 2 美分，5 美分和 10 美分。 请注意，数量是无限的。

![e6b02c4b21565a40ee2b84900be3d40a.png][]

**基本情况：**

*  如果`amount (总金额) = 0`，那么只有一个组合情况：`0`，初始化应该赋值为 `1`。
 *  如果`amount (总金额) > 0`，则组合情况为 `0`。

![378c84ffe73f0d8a3bdef5523b5ab0d0.png][]

**二美分：**

![c04a2a828760f8760c7aca7b54f7b668.png][]

**二美分+五美分：**

*  我们增加 `5` 美分的情况，公式是一样的。

![a4cb60cd4f122f7ddd642cae2ec61687.png][]

**二美分+五美分+十美分：**

*  对于 `10` 美分也是一样的。

![9d96df2cc81fc8ae3f17b9b7da19ef42.png][]

class Solution { 
        public int waysToChange(int n) { 
            int maxAmount = n + 1;
            int[] coins = new int[]{ 1, 5, 10, 25};
            int[] dp = new int[maxAmount];
            dp[0] = 1;
            for (int coin : coins) { 
                for (int x = coin; x < maxAmount; x++) { 
                    dp[x] = dp[x] + dp[x - coin];
                    dp[x] %= 1000000007;
                }
            }
            return dp[n];
        }
    }

[05db8bf07ac0abf2e64490b0fe46c5bc.png]: /images/20221014/8517c2321f7e4ee8966eaa613ded88e1.png
[897464d6e839ab0e3530d0da1ee85873.png]: /images/20221014/0f5e8b77c1b74665873f8fccdad021ac.png
[82b3f7d81c91d7c2e721ec7d5fd68bbb.png]: /images/20221014/0fd5538d3ad74bea8399569f3aeb7f46.png
[7103c15923783092a6ee4c93ada79a74.png]: /images/20221014/4b84aacd5a1d40f297e8eb562ffcbf30.png
[4544660dc2536487db0156bb85b4c3f4.png]: /images/20221014/bf668fee6f7e439ea1c359ae7de6fe11.png
[92a81ee7f5521150c5a2acf9deb8c775.png]: /images/20221014/998eeda7482f49c5bfac8d4d3a7ebc70.png
[a6e0d3e19daa2e13ebef6a2e80cf678a.png]: /images/20221014/42c40742e23842e08e79fc191632c8a6.png
[74783774d3499f814e3c600127c8204b.png]: /images/20221014/b0960893031e4cc28dde0c0cdef10235.png
[2c595d40f724873898a915cfd90e17ce.png]: /images/20221014/9bb1e19c6d154f7c956e8e1f5e2a3279.png
[Offer 14- I.]: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
[ad2718fb6b96ee51b4fd10deb112e87b.png]: /images/20221014/4c0210a3340944b3b8b608f275b25968.png
[a4245551f0fa20e045683836941ad3a2.png]: /images/20221014/97182533ce6a4ea1b4193bf54853cd3d.png
[ca2b4943cc2ad2eb9712b1bcfca0577c.png]: /images/20221014/ea2dbcfa4bfe466891e3ed08d878828f.png
[7b985fcd76b53db0ae4a7328a2c3b7a5.png]: /images/20221014/97ba6bc041bc45ae80e3c42be4f9cdb0.png
[661ac955a1700eda718ce56ec2d8111f.png]: /images/20221014/fc17ab1306df47fe81af355aa73b9178.png
[80374f1290249cad33045a6e18b65b5c.png]: /images/20221014/33c20579105a4b49ad8f8d5e04368512.png
[30e9c5363a07a4f1f4ec6bd6a78dcf9e.png]: /images/20221014/9e2a5dc0a5bb4582a238db2bd781d909.png
[2180f6bbcbb7af8defe3cd8b9c7e54eb.png]: /images/20221014/54192842b5674931ab9ed82d5ea775dc.png
[378c84ffe73f0d8a3bdef5523b5ab0d0.png]: /images/20221014/94cf9a2e4c8d498cb795dbcba4fafd11.png
[19104017574bf8b41b3517850b3bbf7f.png]: /images/20221014/d6e8d892958545dea96f967c0a8eeb26.png
[de60eaa294d97aa1d551e4824d508bfa.png]: /images/20221014/300618cd02ba4605b0b19e299c33c471.png
[a58ddaaf580a641e508cddc2bbbb746c.png]: /images/20221014/05bc35fb2a004434b33b7003a5f79981.png
[92a6a288c436288a3c08568e16a64d0f.png]: /images/20221014/f1b6dbf1c83c4597b42fa1f84e65cf67.png
[d1e35a8c3de25de9b586f466d9b4dca0.png]: /images/20221014/00ecb0ed7eda48b396bf1dbf35865bd3.png
[0bd29b746bd31c42319ab088dbaa568e.png]: /images/20221014/bf8b7956ab9c43dc95d1b4fdcfcb1443.png
[0d1a7b2ce40ac50fe8a3ea877106cc29.png]: /images/20221014/8203573ec6f04b9f92fa841e543630fe.png
[ad6c49fe794fc95e0b0988e72e21fbad.png]: /images/20221014/be3425caae794e8c9b76a22d720c5b68.png
[62.]: https://leetcode-cn.com/problems/unique-paths/
[b17c88ab27b66ef737de45ee520c5398.png]: /images/20221014/5a5469ba3b0b4ad49f73de78698a383d.png
[7cd8f52c160b574a435cb1fa2a9ead0c.png]: /images/20221014/01098795615d47208596e972564c9032.png
[f49380558ef7d323dee90bc3c26b4f94.png]: /images/20221014/02a9e0a35d62480e8dadcfadaebfb8ed.png
[1cc34ca0850f1ca3761370cd546ea45f.png]: /images/20221014/42c86fee2c3646c4b960c2586dceff22.png
[37a19d5d1bd6fa2cab240076333a9716.png]: /images/20221014/0e4d07a3af0e42d8bbd2fc1cd8a456d6.png
[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[f48dc210de290eb35f28a3fbebd8a762.png]: /images/20221014/78cbab81808643979ebc90a76f414d4d.png
[b3e654c102f3e0fa2c012c614a6d1a6d.png]: /images/20221014/f807997e9ce840ac9dc695d833366701.png
[84397e6ef2335ceb53949918034ed2bd.png]: /images/20221014/e329d9b00cb548df92d88abbc1885516.png
[d8933b95d0993ddf22a699384702668a.png]: /images/20221014/d5e153c8787d49b2af09480e5479e94a.png
[6f9e7fce8802e3792dba722b532733ef.png]: /images/20221014/a7968ffe305b439abd7e1a4597eb81f6.png
[122. _ II]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
[123. _ III]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
[188. _ IV]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
[714.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[309.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[343.]: https://leetcode-cn.com/problems/integer-break/
[64.]: https://leetcode-cn.com/problems/minimum-path-sum/
[c605992c817a45901e5e9383c3988dde.png]: /images/20221014/0de020cd5f854fa7bf178df8dd90e3b2.png
[9f6d843a389b5a2bc0c48348e0c7b141.png]: /images/20221014/951d1c40e41b4d7fb1bf445241ae37d8.png
[19c3e4e95a280e03605f60d883697d6c.png]: /images/20221014/b2c3e693dd7244a3ad6d6362240d61c8.png
[e6b02c4b21565a40ee2b84900be3d40a.png]: /images/20221014/d04cdf5c16cc4d0b876f80a3c236d078.png
[c04a2a828760f8760c7aca7b54f7b668.png]: /images/20221014/b2f20c8150f94869b4a3e9842888c03d.png
[a4cb60cd4f122f7ddd642cae2ec61687.png]: /images/20221014/05e7fef831ed40109dd2f35dd2796abd.png
[9d96df2cc81fc8ae3f17b9b7da19ef42.png]: /images/20221014/5eea1e11a8e444158bfec796ce0d3d9e.png