题目汇总
以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。
目前范围：Leetcode前150题
动态规划题目
一维DP
一维DP需要的就是清晰的思路，每个题都变化很大
Longest Valid Parentheses/最长有效括号
找出一个只包含”(“和”)”的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配。Maximum Subarray/ 最大子序和
由 N 个整数元素组成的一维数组 (A[0], A[1],…,A[n-1], A[n])，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？Climbing Stairs/爬楼梯
一共有n级楼梯，每次能够爬一级或两级，共有多少种不同的爬法爬到顶端。注意：第一级楼梯也要上，也就是说第二个楼梯就有两种走法。Decode Ways/解码方法
现在有如下的字母与数字的对应关系：1-A, 2-B, …26-Z。给定一个由数字组成的字符串，判断按照上面的映射可以转换成多少种不同的字符串。(比爬楼梯需要多考虑情况)Unique Binary Search Trees/不同的二叉查找树
给出一个n，求1-n能够得到的所有二叉搜索树Triangle/三角形最小路径和
将一个二维数组排列成金字塔的形状，找到一条从塔顶到塔底的路径，使路径上的所有点的和最小，从上一层到下一层只能挑相邻的两个点中的一个。Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II
将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求最少需要几次分割能够满足需求。Word Break/Word Break II/单词拆分/单词拆分 II
给定一个目标字符串和一组字符串，判断目标字符串能否拆分成数个字符串，这些字符串都在给定的那组字符串中。Best Time to Buy and Sell Stock I/II/III/买卖股票的最佳时机
给定每天的股票价格，如果只允许进行一轮交易，也就是买进一次和卖出一次，求所能获得的最大的利润。
二维DP
布尔数组
Longest Palindromic Substring/最长回文子串
给出一个字符串S，找到一个最长的连续回文串。Interleaving String/交错字符串
输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交替而成且不改变s1和s2中各个字符原有的相对顺序。
数字数组
0-1背包
0-1背包问题-
- 完全背包问题与01背包问题的区别在于每一件物品的数量都有无限个，而01背包每件物品数量只有一个。
- 多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。
Unique Paths/Unique Paths II/不同路径
机器人从起点到终点有多少条不同的路径，只能向右或者向下走。Minimum Path Sum/最小路径和
一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。Edit Distance/编辑距离
求两个字符串之间的最短编辑距离，即原来的字符串至少要经过多少次操作才能够变成目标字符串，操作包括删除一个字符、插入一个字符、更新一个字符。Distinct Subsequences/不同子序列
给定S和T两个字符串，问把通过删除S中的某些字符，把S变为T有几种方法？补充：京东2019实习编程题-删除0或部分字符使其成为回文串
见笔试整理总结补充：爱奇艺2019实习编程题-n种糖果，每个盒子m个，每个糖果有最小最大限制，求多少种放法
见网页
三维DP
- Scramble String/扰乱字符串
给出两个等长的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
京公网安备 11010502036488号