【LeetCode算法笔记】Day1:动态规划基础

动态规划简介

动态规划的定义

简称DP,是一种求解多阶段决策过程最优化问题的方法。在动态规划中，通过把原问题分解为相对简单的子问题，先求解子问题，再由子问题而得到原问题的解

动态规划的核心思想

• 把原问题分解为若干个重叠的子问题，每个子问题求解过程都构成一个阶段。在完成一个阶段的计算之后，动态规划放过发会执行下一阶段的计算
• 在求解字问题的构成中，按照自顶向下的记忆化搜索方法或者自底向上的递推方法求解出子问题的解，把结果存储在表格中，当需要再次求解子问题时，直接从表格中查询该子问题的解，从而避免大量的重复计算。

动态规划的简单例子

从图中可以看出：如果使用传统的递归算法计算f(5),需要先计算f(3)和f(4),而在计算f(4)时还需要计算f(3),这样f(3)就进行了多次计算。同理f(0)、f(1)、f(2)都进行了动词计算，从而导致了重复计算问题。

为了避免重复计算，我们可以使用动态规划中表格处理方法来处理。

这里我们使用自底向上的递推方法求解出子问题f(n-2)和f(n-1)的解，然后把结果存储在表格中，供随后的计算查询使用。

• 定义一个数组dp，用于记录斐波那契数列中的值
• 初始化dp[0]=0,dp[1]=1.
• 根据斐波那契数列的递推公式f(n)=f(n-1)+f(n-2),从dp(2)开始递推计算斐波那契列的每个数，直接计算出dp(n).
• 最后返回dp(n)即可得到第n项斐波那契值

class Solution:
    def fib(self,n):
        if n==0:
            return 0
        if n==1:
            return 1

        dp = [0 for _ in range(n+1)]
        dp[0]=0
        dp[1]=1

        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]

        return dp[n]


if __name__ == '__main__':
    solution=Solution()
    result = solution.fib(5)
    print(result)

这里使用缓存(哈希表、集合或数组)保存计算结果，从而避免子问题重复计算的方法，就是动态规划算法

动态规划特征

能够使用动态规划方法解决问题必须满足以下三个特征

• 最优子结构性质
• 重叠子问题性质
• 无后效性

最优子结构性质

最优子结构：指的是一个问题的最优解包括子问题的最优解

重复子问题性质

重叠子问题性质：指的是在求解子问题的过程中，有大量的子问题是重复的，一个子问题在下一阶段的决策中可能会被多次用到。如果有大量重复的子问题，那么只需要对其求解一次，然后用表格将结果存储下来，以后使用时可以直接查询，不需要再次求解。

无后效应

无后效性：指的是子问题的解（状态值）只与之前阶段有关，而与后面阶段无关。当前阶段的若干状态值一旦确定，就不再改变，不会再受到后续阶段决策的影响。

也就是说，一旦某一个子问题的求解结果确定以后，就不会在被修改

动态规划的基本思路

如下图所示，我们在使用动态规划方法解决某些最优化问题时，可以将解决问题的过程按照一定顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的「阶段」。然后按照顺序对每一个阶段做出「决策」，这个决策既决定了本阶段的效益，也决定了下一阶段的初始状态。依次做完每个阶段的决策之后，就得到了一个整个问题的决策序列。

这样就将一个原问题分解为了一系列的子问题，再通过逐步求解从而获得最终结果。

这种前后关联，具有链状结构的多阶段进行决策的问题叫做多阶段洁厕问题

通常我们使用动态规划方法来解决问题的基本思路如下：

• 划分阶段：将原问题按顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的「阶段」。划分后的阶段⼀定是有序或可排序的，否则问题⽆法求解。
  这里的「阶段」指的是⼦问题的求解过程。每个⼦问题的求解过程都构成⼀个「阶段」，在完成前⼀阶段的求解后才会进⾏后⼀阶段的求解。

• 定义状态：将和子问题相关的某些变量（位置、数量、体积、空间等等）作为一个「状态」表示出来。状态的选择要满⾜⽆后效性。

• 转移状态：根据「上一阶段的状态」和「该状态下所能做出的决策」，推导出「下一阶段的状态」。或者说根据相邻两个阶段各个状态之间的关系，确定决策，然后推导出状态间的相互转移方式（即「状态转移方程」）。

• 初始化条件和边界条件：根据问题描述、状态定义和状态转移方程，确定初始条件和边界条件

• 最终结果：确定问题的求解目标，然后按照一定顺序求解每一个阶段的问题。最后根据状态转移方程的递推结果，确定最终结果。