[Leetcode][动态规划]相关题目汇总/分析/总结

题目汇总

以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。

目前范围：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中各个字符原有的相对顺序。

数字数组

• 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 的扰乱字符串。

动态规划总结