• 1. 实践报告分析
  • 1.1 问题描述
  • 1.2 算法描述
  • 1.3 问题求解
    • 1.1.1 根据最优子结构性质，列出递归方程式
    • 1.1.2 给出填表法中表的维度、填表范围和填表顺序
    • 1.1.3 分析该算法的时间和空间复杂度
  • 1.3 心得体会
• 2. 对动态规划算法的理解和体会

1. 实践报告分析

1.1 问题描述

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列

1.2 算法描述

输入一个序列，将其排序得到一个新的序列，并且是递增的，我们就可以将问题转化为求原序列和新序列的最长公共子序列
运用动态规划的思想，我们将子问题的结果继续在一个二维数组中，再根据这个二维数组中的值得到最长公共子序列

1.3 问题求解

原序列保存在数组b中，排序后的原序列保存在数组a中
定义一个二维数组c[][]用于保存子问题的结果

1.1.1 根据最优子结构性质，列出递归方程式

首先给出一个问题表示c[i,j]：a[1...i]和b[1...j]的最长公共子序列，那么我们就可以明确原始问题为c[n,n]：a[1...n]和b[1...n]的最长公共子序列
我们要寻找的最长公共子序列就保存在c[n][n]中
我们分析序列a和序列b的末尾字符，（这里假设末尾字符为第n位字符），可以分为两种情况：

1. 末尾字符不相等
2. 末尾字符相等

针对这两种情况，（细节分析在这里不过多阐述），我们可以得到递推公式：

c[i,j] = {
            max{c[i-1,j],c[i,j-1]} (ai != bj)
            c[i-1,j-1]+1 (ai = bj)
          }

1.1.2 给出填表法中表的维度、填表范围和填表顺序

表的维度：数组c为二维数组
填表范围：n行n列
填表顺序：自左向右，自底向上

1.1.3 分析该算法的时间和空间复杂度

时间复杂度：主要看双重循环填表的那部分，时间复杂度为O(n^2)
空间复杂度：需要填一个n行n列的表，空间复杂度为O(n^2)

1.3 心得体会

这次实践课让我能更熟练地运用动态规划解决问题。这道题在填表的时候卡在了一个细节位置，我按照了以前的习惯写二重循环的时候写了i<n，而不是i<=n，导致填的表少了一行一列，并且找了好久才找出来，这也让我对动态规划填表时的循环条件有了更深刻的印象

2. 对动态规划算法的理解和体会

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是动态规划算法经分解得到的子问题往往不是互相独立的，使用动态规划算法的问题一般具有最优子结构性质和重叠子问题性质，我们就可以借助这个问题的最优子结构性质列出递归式从而求解
动态规划解题四步骤：1.问题结构分析 2.递推关系建立 3.自底向上计算 4.最优方案追踪