动态规划——青岛大学19软件1班黄增尧

目录

• 矩阵链乘问题
• • 题目描述
  • 解决思路
  • 代码
• 最长公共子序列
• • 题目描述
  • 解决思路
  • 代码
• 0-1背包问题
• • 题目描述
  • 解决思路
  • 代码
• 最小m段和问题
• • 题目描述
  • 解决思路
  • 代码

矩阵链乘问题

题目描述

有若干个矩阵{Ai}，元素都为整数且已知矩阵大小。
如果要计算所有矩阵的乘积A1 * A2 * A3 … Am，最少要多少次整数乘法/p>

解决思路

最优子结构：m[i][j]：第i个矩阵到第j个矩阵链乘成为一个矩阵的最少乘法次数。
状态转移方程：m[i][j] = max(m[i][j], m[i][k] + m[k + 1][j] + p[i – 1] * p[k] * p[j])。

代码

最长公共子序列

题目描述

给定一个序列X=，另一个序列Z=，若存在一个严格递增的X的下标序列对所有的1,2,3,…,k，都满足x(ik)=zk，则称Z是X的子序列，求两个给定字符串X、Y的最长公共子序列Z。
例：Z=是X=的子序列

解决思路

最优子结构：dp[i][j]：从X开始处到X[i]的子串与从Y开始处到Y[j]的子串的最长公共子序列长度。
状态转移方程：
dp[i][j]=dp[i-1][j-1]+1 (a[i]=b[j])
dp[i][j]=max(dp[i-1][j],dp[i][j-1])

代码

0-1背包问题

题目描述

给定n种物品和一个背包容量m，物品i的重量、价值为a [i], b [i]，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大/p>

解决思路

原数组a [i], b [i]，结果数组c [i][j]，路径数组d [i][j]。
状态转移方程：
当j>=a [i]&&c [i][j]=a [i]&&c [i][j] 否则，c [i][j] = c [i-1][j]。
物理意义：
c [i][j]为把前i个物品装进容量为j的背包的最佳方案的所装物品总价值。

代码

最小m段和问题

题目描述

给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小/p>

解决思路

最优子结构：b[i][j]： i个数字划分j段的最大值的最小值。
状态转移方程：b[i][j]=min{max{b[i][1]-b[k][1],b[k][j-1]}} (1 b [n][m]即为最终结果。

代码

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33815 人正在系统学习中