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

超、凢脫俗 2022-05-27 08:54 204阅读 0赞

## 题目汇总 ##

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

目前范围：Leetcode前150题

### 动态规划题目 ###

#### 一维DP ####

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

*  [Longest Valid Parentheses/最长有效括号][Longest Valid Parentheses]  
    找出一个只包含”(“和”)”的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配。
 *  [Maximum Subarray/ 最大子序和][Maximum Subarray_]  
    由 N 个整数元素组成的一维数组 (A\[0\], A\[1\],…,A\[n-1\], A\[n\])，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？
 *  [Climbing Stairs/爬楼梯][Climbing Stairs]  
    一共有n级楼梯，每次能够爬一级或两级，共有多少种不同的爬法爬到顶端。注意：第一级楼梯也要上，也就是说第二个楼梯就有两种走法。
 *  [Decode Ways/解码方法][Decode Ways]  
    现在有如下的字母与数字的对应关系：1-A, 2-B, …26-Z。给定一个由数字组成的字符串，判断按照上面的映射可以转换成多少种不同的字符串。(比爬楼梯需要多考虑情况)
 *  [Unique Binary Search Trees/不同的二叉查找树][Unique Binary Search Trees]  
    给出一个n，求1-n能够得到的所有二叉搜索树
 *  [Triangle/三角形最小路径和][Triangle]  
    将一个二维数组排列成金字塔的形状，找到一条从塔顶到塔底的路径，使路径上的所有点的和最小，从上一层到下一层只能挑相邻的两个点中的一个。
 *  [Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II][Palindrome Partitioning_Palindrome Partitioning II_II]  
    将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求最少需要几次分割能够满足需求。
 *  [Word Break/Word Break II/单词拆分/单词拆分 II][Word Break_Word Break II_ II]  
    给定一个目标字符串和一组字符串，判断目标字符串能否拆分成数个字符串，这些字符串都在给定的那组字符串中。
 *  [Best Time to Buy and Sell Stock I/II/III/买卖股票的最佳时机][Best Time to Buy and Sell Stock I_II_III]  
    给定每天的股票价格，如果只允许进行一轮交易，也就是买进一次和卖出一次，求所能获得的最大的利润。

#### 二维DP ####

##### 布尔数组 #####

*  [Longest Palindromic Substring/最长回文子串][Longest Palindromic Substring]  
    给出一个字符串S，找到一个最长的连续回文串。
 *  [Interleaving String/交错字符串][Interleaving String]  
    输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交替而成且不改变s1和s2中各个字符原有的相对顺序。

##### 数字数组 #####

*  [0-1背包][0-1]  
    0-1背包问题
 *  [完全背包、多重背包][Link 1]
    
     *  完全背包问题与01背包问题的区别在于每一件物品的数量都有无限个，而01背包每件物品数量只有一个。
     *  多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。
 *  [Unique Paths/Unique Paths II/不同路径][Unique Paths_Unique Paths II]  
    机器人从起点到终点有多少条不同的路径，只能向右或者向下走。
 *  [Minimum Path Sum/最小路径和][Minimum Path Sum]  
    一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。
 *  [Edit Distance/编辑距离][Edit Distance]  
    求两个字符串之间的最短编辑距离，即原来的字符串至少要经过多少次操作才能够变成目标字符串，操作包括删除一个字符、插入一个字符、更新一个字符。
 *  [Distinct Subsequences/不同子序列][Distinct Subsequences]  
    给定S和T两个字符串，问把通过删除S中的某些字符，把S变为T有几种方法？
 *  补充：京东2019实习编程题-[删除0或部分字符使其成为回文串][0]  
    见笔试整理总结
 *  补充：爱奇艺2019实习编程题-[n种糖果，每个盒子m个，每个糖果有最小最大限制，求多少种放法][n_m]  
    见网页

#### 三维DP ####

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

### 动态规划总结 ###

[Longest Valid Parentheses]: https://blog.csdn.net/qqxx6661/article/details/77876647
[Maximum Subarray_]: https://blog.csdn.net/qqxx6661/article/details/78167981
[Climbing Stairs]: https://blog.csdn.net/qqxx6661/article/details/78245823
[Decode Ways]: https://blog.csdn.net/qqxx6661/article/details/78389583
[Unique Binary Search Trees]: https://blog.csdn.net/qqxx6661/article/details/76285972
[Triangle]: https://blog.csdn.net/qqxx6661/article/details/78474268
[Palindrome Partitioning_Palindrome Partitioning II_II]: https://blog.csdn.net/qqxx6661/article/details/78546764
[Word Break_Word Break II_ II]: https://blog.csdn.net/qqxx6661/article/details/78737010
[Best Time to Buy and Sell Stock I_II_III]: https://blog.csdn.net/qqxx6661/article/details/78463652
[Longest Palindromic Substring]: https://blog.csdn.net/qqxx6661/article/details/76864410
[Interleaving String]: https://blog.csdn.net/qqxx6661/article/details/78441025
[0-1]: https://blog.csdn.net/qqxx6661/article/details/56678345
[Link 1]: https://blog.csdn.net/na_beginning/article/details/62884939
[Unique Paths_Unique Paths II]: https://blog.csdn.net/qqxx6661/article/details/78231730
[Minimum Path Sum]: https://blog.csdn.net/qqxx6661/article/details/78231736
[Edit Distance]: https://blog.csdn.net/qqxx6661/article/details/78268742
[Distinct Subsequences]: https://blog.csdn.net/qqxx6661/article/details/78447473
[0]: https://www.nowcoder.com/discuss/72829
[n_m]: https://www.nowcoder.com/discuss/76124
[Scramble String]: https://blog.csdn.net/qqxx6661/article/details/79895861