动态规划的介绍

基本思想

动态规划算法的基本思想是：将带求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解中得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，避免重复求解。该思想与记忆化搜索类似，即将计算步骤中的过程保存下来，避免重复运算

要点

动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题

需要记录每个子问题求解的问题结果，以供其他问题进行解决

相关步骤

1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

2、确定状态和状态变量：注意状态必须满足无后效性。

3、确定决策：找到子问题是进行动态规划的重要一步。动态规划和递推更多应考虑本问题由哪些已解决子问题构成，而不是考虑本问题对将来哪些问题有贡献。

4、确定边界条件，写出状态转移方程

相关例题讲解

题目要求

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

输入：triangle = [[-10]]
输出：-10

思路

在本题中，给定的三角形的行数为 n，并且第 ii 行（从 00 开始编号）包含了 i+1 个数。如果将每一行的左端对齐，那么会形成一个等腰直角三角形，如下所示：

[2]
[3,4]
[6,5,7]
[4,1,8,3]

我们用 f[i][j] 表示从三角形顶部走到位置 (i, j) 的最小路径和。这里的位置 (i, j) 指的是三角形中第 i 行第 j 列（均从 00 开始编号）的位置。

由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置 (i, j)，上一步就只能在位置 (i - 1, j - 1)或者位置 (i - 1, j)。我们在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为：

f[i][j] = min(f[i-1][j-1], f[i-1][j]) + c[i][j]
f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]

其中 c[i][j] 表示位置 (i, j) 对应的元素值。

注意第 i 行有 i+1个元素，它们对应的 j 的范围为 [0, i]。当 j=0或 j=i 时，上述状态转移方程中有一些项是没有意义的。例如当 j=0 时，f[i-1][j-1] 没有意义，因此状态转移方程为：

f[i][0] = f[i-1][0] + c[i][0]
f[i][0]=f[i−1][0]+c[i][0]

即当我们在第 i 行的最左侧时，我们只能从第 i-1行的最左侧移动过来。当 j=i时，f[i-1][j] 没有意义，因此状态转移方程为：

f[i][i] = f[i-1][i-1] + c[i][i]
f[i][i]=f[i−1][i−1]+c[i][i]

即当我们在第 i 行的最右侧时，我们只能从第 i-1 行的最右侧移动过来。

最终的答案即为 f[n-1][0] 到 f[n-1][n-1]中的最小值，其中 n 是三角形的行数。

细节

状态转移方程的边界条件是什么？由于我们已经去除了所有「没有意义」的状态，因此边界条件可以定为：

f[0][0] = c[0][0]
f[0][0]=c[0][0]

即在三角形的顶部时，最小路径和就等于对应位置的元素值。这样一来，我们从 1 开始递增地枚举 i，并在 [0, i]的范围内递增地枚举 j，就可以完成所有状态的计算。

代码

def minimumTotal(triangle):
    size = len(triangle)
    if size == 0:
        return -1
    dp = [[0] * size for i in range(size)]
    dp[0][0] = triangle[0][0]
    for i in range(1, size):
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        for j in range(1, i):
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
        dp[i][i] = dp[i-1][i-1] + triangle[i][i]
    return min(dp[size-1])

其他例题

题目要求

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 ：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

题解

    def rob(nums):
        x = len(nums)
        if x == 0:
            return 0
        if x == 1:
            return nums[0]
        dp = [0] * x
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, x):
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
        return dp[x - 1]