算法理论——动态规划(一看就会)

简介: 动态规划算法的基本思想是:将带求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解中得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,避免重复求解。

动态规划的介绍

基本思想

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

要点

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

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

相关步骤

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]


目录
相关文章
|
12天前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
194 1
|
11月前
|
存储 算法
深入了解动态规划算法
深入了解动态规划算法
249 1
|
7月前
|
存储 算法 Java
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
267 4
算法系列之动态规划
|
11月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
158 8
|
8月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
217 5
|
7月前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
|
7月前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
|
11月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
502 2
动态规划算法学习三:0-1背包问题
|
10月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
202 2

热门文章

最新文章