动态规划算法的案例

1. 最长公共子序列

给定两个字符串，求它们的最长公共子序列。

例如，对于字符串 "ABCD" 和 "EACB"，它们的最长公共子序列为 "AC"。

2. 背包问题

给定一个背包和一些物品，每个物品有自己的重量和价值，选择一些物品放入背包中使得总重量不超过背包容量，同时价值最大。

3. 斐波那契数列

在斐波那契数列中，每个数都是前两个数的和，例如，0、1、1、2、3、5、8、13、21、34、55、89、144、233、377……。

4. 最长上升子序列

给定一个序列，找到其中的最长上升子序列。

例如，对于序列 {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9}，它的最长上升子序列为 {1,2,3,5,8,9}。

5. 最大子段和

给定一个序列，找到其中的一个子段，使得子段中的元素和最大。

例如，对于序列 {-2,1,-3,4,-1,2,1,-5,4}，最大子段为 {4,-1,2,1}，其和为6。