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

题目汇总

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

目前范围：Leetcode前150题

动态规划题目

一维DP

一维DP需要的就是清晰的思路，每个题都变化很大

• Longest Valid Parentheses/最长有效括号 找出一个只包含”(“和”)”的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配。
• Maximum Subarray/ 最大子序和 由 N 个整数元素组成的一维数组 (A0, A1,…,An-1, An)，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？
• 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背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。

三维DP

• Scramble String/扰乱字符串 给出两个等长的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

动态规划总结