动态规划

1. 乘积最大子数组

问题：给你一个整数数组 numbers，找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），返回该子数组的乘积。

示例1：输入: [2,7,-2,4]输出: 14解释: 子数组 [2,7] 有最大乘积 14。

示例2：输入: [-5,0,3,-1]输出: 3解释: 结果不能为 15, 因为 [-5,3,-1] 不是子数组，是子序列。

1. 最长回文子串

问题：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1：输入: "babad"输出: "bab"

2：输入: "cbbd"输出: "bb"

1. 最长上升子序列

问题：给定一个无序的整数数组，找到其中最长上升子序列的长度。可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

示例：输入: [10,9,2,5,3,7,66,18]输出: 4解释: 最长的上升子序列是 [2,3,7,66]，它的长度是 4。

求可行性（True 或 False）

1. 凑零兑换问题

问题：给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。 示例1：输入: c1=1, c2=2, c3=5, c4=7, amount = 15输出: 3解释: 11 = 7 + 7 + 1。

示例2：输入: c1=3, amount =7输出: -1解释: 3怎么也凑不到7这个值。

1. 字符串交错组成问题问题：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例1：输入: s1="aabcc",s2 ="dbbca",s3="aadbbcbcac"输出: true解释: 可以交错组成。示例2：输入: s1="aabcc",s2="dbbca",s3="aadbbbaccc"输出: false解释:无法交错组成。