动态规划的基本原理和基本应用动态规划（Dynamic Programming）是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。
动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题，以减少不必要的重复计算。
它在计算机科学和数学中具有广泛的应用，尤其是在优化、组合数学和操作研究等领域。
1.确定最优子结构：将原问题分解为较小的子问题，并且子问题的最优解能够推导出原问题的最优解。
2.定义状态：确定存储子问题解的状态变量和状态方程。
3.确定边界条件：确定初始子问题的解，也称为边界状态。
4.递推计算：利用状态方程将子问题的解计算出来，并存储在状态变量中。
5.求解最优解：通过遍历状态变量找到最优解。
1.背包问题：背包问题是动态规划的经典应用之一、它有多种变体，其中最基本的是0/1背包问题，即在限定容量的背包中选择物品，使得所选物品的总价值最大。
可以使用动态规划的思想来解决背包问题，确定状态为背包容量和可选物品，递推计算每个状态下的最优解。
2. 最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是一种常见的子序列问题。
给定一个序列，找到其中最长的递增子序列。
可以使用动态规划来解决这个问题，状态可以定义为以第i个元素为结尾的最长递增子序列的长度，并递推计算每个状态的解。
3.矩阵链乘法：矩阵链乘法是一种优化矩阵连乘计算的方法。
给定一系列矩阵，求解它们相乘的最小计算次数。
可以使用动态规划解决矩阵链乘法问题，状态可以定义为矩阵链的起始和结束位置，递推计算每个状态下最小计算次数。
4.最短路径问题：最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。
可以使用动态规划解决最短路径问题，状态可以定义为起始节点到一些节点的最短距离，递推计算每个状态的最优解。
第七章动态规划｛最长公共子序列、矩阵链乘、点对最短路径｝仅供参考7.5用算法LCS来找出两个字符串A=”xzyzzyx”和B=”zxyyzxz”的最长公共子序列的长度。
给出一个最长公共子序列。
解：算法LCS填表过程如下：由回溯法以求得最长公共子序列（长度为4）有以下两个：1.（上行方向回溯）:xyyz，逆序zyyx为所求。
2.（左行方向回溯）:zzyx，逆序xyzz为所求。
7.11对于以下5个矩阵应用算法MATCHAINM1：2*3，M2：3*6，M3：6*4，M4：4*2，M5：2*7 （a）找出这5个矩阵相乘需要的最小数量算法的次数（即C[1,5]）。
（b）请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。
解：矩阵链乘算法MATCHAIN。
建立矩阵C[n][n],其中Cij表示矩阵i到j的链乘的最小次数。
递归式如下：{}{)(,0,**],[]1,[min 1],[j i if j k i r r r j k C k i C j k i j i C =<=<++-+=目标为C[1,n]。
过程如下表：M1:2×3 M2:3×6 M3:6×4 M4:4×2 M5:2×7 首先，为了找出这五个矩阵相乘需要的最少数量乘法的次数的结合方法，使用动态规划方法，填写二维表C 。
r 为记录顺序规模的数组｛2，3，6，4，2，7｝. 动态规划的填表公式如下：C[i,j]=min{C[i,k-1]+C[k,j]+r i r k r j+1}，并且通过加括号指出当前规模的结合方式。
所以，这五个矩阵相乘需要的最少数量乘法的次数为：124 最佳乘法结合次序为如下表达式：(M1(M2(M3M4)))M57.15在如图7.7所示的含权有向图上执行所有点对最短路径算法。
解：记L[i,j]为初始状态点i 到点j的路径长；k j i d ,为矩阵k D 的第i 行j 列元素，表征从点i 到点j ，除了可能经过顶点1、顶点2或者同时经过他们以外，不经过任何其他顶点的最短路径，等等。
