动态规划(Dynamic Programming)是算法的一种类型，它通过将某个复杂问题分解为子问题，通过解决子问题并保存子问题的结果，避免重新计算同样的子问题，进而解决原来的复杂问题。
如果某个问题具有下面两个属性，那么它可能适合于用动态规划算法来解决：
1）重叠的子问题（Overlapping Subproblems）
2）最优的子结构（Optimal Substructure）
在上节课中，我们介绍了动态规划的第一个属性——重叠的子问题。
本课介绍它的第二个属性——最优的子结构。
最优的子结构
我们来看看什么是最优的子结构。
最优的子结构：对于一个给定的问题，如果通过利用其子问题的最优解，可以获得给定问题的最优解，那么我们说这个给定问题具有最优子结构属性。
例如，最短路径问题具有以下最优子结构属性：
如果节点x位于从源节点u到目的节点v的最短路径中，则从u到v的最短路径是从u到x的最短路径和从x到v的最短路径的组合。
因此求两个节点之间的最短路径的一些标准算法，例如：Floyd-Warshall算法和Bellman-Ford算法，都是采用动态编程来解决问题的典型例子。
另一方面，最长路径问题没有最佳子结构属性。这里的最长路径是指两个节点之间最长的简单路径（没有循环的路径）。
我们看下面的例子。
从q到t有两条最长的路径：q→r→t和q→s→t。与最短路径不同，这些最长路径不具有最佳子结构属性。
例如，最长路径q→r→t不是从q到r的最长路径和从r到t的最长路径的组合：
因为从q到r的最长路径是q→s→t→r；从r到t的最长路径是r→q→s→t。
q→r→t 不等于 q→s→t→r + r→q→s→t
所以找q到t的最长路径不能拆分为找q到r的最长路径和r到t的最长路径的组合的方式，因此它不具备最优的子结构的特性。
最长递增序列问题
以最长递增子序列（LIS）问题为例，我们一起看看如何使用动态规划来解决它。
最长递增子序列（LIS）问题是用于找出给定序列的中一个最长子序列，使得子序列的所有元素按递增顺序排序。 例如，对于序列{10,22,9,33,21,50,41,60,80}，它的子序列{10,22,33,50,60,80}中的元素依次递增排列，具有最长的长度，所以它的LIS长度为6。
更多的例子：
输入: arr[] = {3, 10, 2, 1, 20}
输出: Length of LIS = 3
最长的递增序列为3, 10, 20
输入: arr[] = {3, 2}
输出: Length of LIS = 1
最长的递增序列为{3} and {2}
输入:arr[] = {50, 3, 10, 7, 40, 80}
输出:Length of LIS = 4
最长的递增序列 {3, 7, 40, 80}
最长递增序列问题的最佳子结构
假设arr [0..n-1]为输入数组，L(i)为在索引i处结束的LIS的长度，arr[i]是LIS的最后一个元素。
这样，L(i) 可以递归写为：
1） L(i) = 1 + max(L(j)）其中0<j<i且arr[j]<arr[i];
2） L(i) = 1，如果不存在这样的j。
要找到给定数组的LIS，我们需要返回max(L(i))，其中0<i<n。因此，我们看到LIS问题满足最优子结构属性，可以使用子问题的解来找出原来问题的解。
下面是上面递归算法的简单实现。
#include<stdio.h>#include<stdlib.h> int _lis( int arr[], int n, int *max_ref){ if (n == 1) return 1; int res, max_ending_here = 1; for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here) max_ending_here = res + 1; } if (*max_ref < max_ending_here) *max_ref = max_ending_here; return max_ending_here;}int lis(int arr[], int n){ int max = 1; _lis( arr, n, &max );
return max;}int main(){ int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr)/sizeof(arr[0]); printf('Length of lis is %dn', lis( arr, n )); return 0;}改成动态规划编程
上述程序实现中，很明显具有重叠的子问题特性。
例如计算lis(4)的过程如下图所示。
很明显，许多相同的lis(k)被重复计算，具备重叠的子问题特性。可以对算法进行优化。
这里采用列表方式的优化方式。改进后的程序的实现如下：
#include<bits/stdc++.h>
using namespace std;
int lis( int arr[], int n )
{
int lis[n];
lis[0] = 1;
for (int i = 1; i < n; i++ )
{
lis[i] = 1;
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
return *max_element(lis, lis+n);
}
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf('Length of lis is %d\n', lis( arr, n ) );
return 0;
}
课后请运行本课中的程序，并思考如何解决下面的最长链问题：
假设有一个包含很多个数字对的集合。在每一个数字对中，第一个数字小于第二个数字。比如，｛（1，3），（2，4），（6，7），（3，9），（4，5）｝。并且对于其中的任何两组数字对（a，b）和（c，d），如果b <c，则（c，d）可以接在（a，b）之后，形成（a，b）—>(c，d）的链条。用类似的方式，可以形成一个长链。请你找到可以形成的最长链。
联系客服
