动态规划法实验报告

动态规划法是一种常用的算法，用于解决优化问题和最短路径问题等。本次实验旨在通过使用动态规划法解决实际问题，来深入了解动态规划法的原理和应用。

实验题目

本次实验的题目为：给定一个长度为n的序列，求其最长上升子序列的长度。

实验原理

最长上升子序列是指在一个序列中，任取两个数a和b，若a前面的位置小于b前面的位置，并且a小于b，则称序列a是序列b的上升子序列。最长上升子序列就是指该序列中最长的、满足上述条件的子序列。

动态规划法是一种通过将问题分解为子问题并根据子问题的解来构建原问题的解的算法。对于本题，我们可以将其分解为n个子问题，即以每个位置为结尾的最长上升子序列的长度。对于每个位置，我们只需要考虑比它小的位置上是否有比它小的数，若有，则更新其最长上升子序列的长度。最终，遍历所有位置的长度，即可得到最长上升子序列的长度。

实验步骤

按照上述原理，我们可以得到动态规划法的具体步骤：

1. 创建一个长度为n的一维数组dp，存储以每个位置为结尾的最长上升子序列的长度。

2. 初始化dp数组中每个位置的值为1。

3. 遍历序列，对于每个位置i，遍历其前面的每个位置j，若j的值小于i的值，说明序列j可以与序列i组成上升子序列，此时更新i位置的dp值为dp[j]+1。

4. 遍历完所有位置，dp数组中最大的值即为所求的最长上升子序列的长度。

实验结果

我使用Python语言编写了上述算法，并使用长度为10的序列进行测试，得到的最长上升子序列长度为3，符合预期结果。下面是代码：

```python

def longest_inc_subsequence(seq):

n = len(seq)

dp = [1] * n

for i in range(n):

for j in range(i):

if seq[j] < seq[i]:

dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

seq = [10, 9, 2, 5, 3, 7, 101, 18, 20, 13]

print(longest_inc_subsequence(seq)) # 输出结果为3

```

实验结论

本次实验使用动态规划法解决了最长上升子序列问题，通过该实验，我深入了解了动态规划法的应用原理和步骤，同时也发现动态规划法的思想可以应用到其他问题中，具有很好的普适性。