LeetCode刷题之动态规划的解题方法及相关练习(二)

た入场券 2023-02-20 12:25 38阅读 0赞

### 往期回顾 ###

[LeetCode刷题之动态规划的解题方法及相关练习(一)][LeetCode]

--------------------

**动态规划所要满足的条件：**

1.  大问题拆分成小问题
2.  小问题会不会被重复调用

--------------------

从集合的角度来考虑DP问题，用某一个数来代表一类数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]

--------------------

**线性DP:**

\[1\]. [快乐的LeetCode — 53.最大子序和][LeetCode _ 53.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            size = len(nums)
            if size == 0: return -2147483648
            f = [nums[0], ]
            for i in range(1, size):
                f.append(max(f[i-1], 0) + nums[i])
            return max(f)

--------------------

\[2\]. [快乐的LeetCode — 120. 三角形最小路径和][LeetCode _ 120.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]

--------------------

\[3\]. [多味的LeetCode — 62. 不同路径][LeetCode _ 62.]  
  [多口味LeetCode — 63. 不同路径 II][LeetCode _ 63. _ II]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]

--------------------

\[4\]. [多味的LeetCode — 91. 解码方法][LeetCode _ 91.]

--------------------

**区间DP问题**

\[5\]. [多味的LeetCode — 198. 打家劫舍][LeetCode _ 198.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 4]

--------------------

\[6\]. [多味的LeetCode — 300. 最长上升子序列][LeetCode _ 300.]

--------------------

\[7\]. [多味的LeetCode — 72. 编辑距离][LeetCode _ 72.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]

\[8\]. [快乐的LeetCode — 面试题42. 连续子数组的最大和][LeetCode _ _42.]  
\[9\]. [快乐的LeetCode — 面试题 08.11. 硬币][LeetCode _ _ 08.11.]  
\[10\]. [快乐的LeetCode — 322. 零钱兑换][LeetCode _ 322.]

**背包DP问题**

[LeetCode]: https://blog.csdn.net/weixin_43283397/article/details/108264137
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200629083540475.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode _ 53.]: https://blog.csdn.net/weixin_43283397/article/details/104531690
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200629083451280.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode _ 120.]: https://blog.csdn.net/weixin_43283397/article/details/106978549
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200629084217825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode _ 62.]: https://blog.csdn.net/weixin_43283397/article/details/104668226
[LeetCode _ 63. _ II]: https://blog.csdn.net/weixin_43283397/article/details/106991895
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200629084727976.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode _ 91.]: https://blog.csdn.net/weixin_43283397/article/details/104960547
[LeetCode _ 198.]: https://blog.csdn.net/weixin_43283397/article/details/107015721
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200701090119662.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode _ 300.]: https://blog.csdn.net/weixin_43283397/article/details/104856302
[LeetCode _ 72.]: https://blog.csdn.net/weixin_43283397/article/details/104811906
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200701155829313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70
[LeetCode _ _42.]: https://blog.csdn.net/weixin_43283397/article/details/106657913
[LeetCode _ _ 08.11.]: https://blog.csdn.net/weixin_43283397/article/details/105700049
[LeetCode _ 322.]: https://blog.csdn.net/weixin_43283397/article/details/107364444