# 邓公数据结构与算法1-算法分析

• 算法分析

• 迭代、递归

• 动态规划

• 级数的大 O 分析

• 循环 vs 级数

## 动态规划

### 记忆法：example Fabonacci

$$fib(n)=fib(n-1)+fib(n-2)$$

• 记忆，通过制表，避免重复调用

• 动态规划：颠倒计算方向，自顶而下递归，转换为自底而上迭代

### example: LCS (longest common sequence)

• n=-1 或 m=-1, 则为空

• A[n] = B[m] = “X”, 减而治之，同时缩小两个字串 LCS(A[0, n-1], B[0, m-1]) + “X”

• $A[n] \ne B[m]$, 分而治之，LCS(A[0, n-1], B[0,m]) 和 LCS(A[0, n],B[0, m-1]) 中的较大值。

• 将所有子问题列成一张表

• 颠倒计算方向，从 LCS(A[0], B[0]) 依次计算所有项。

$m\times n$ 的表格

• 先填入第一行，一个字符为 “3”，没有与之相同的字符，所有这一行都为 0.

• 再填入第二行，填 [2,1] 处，都为3，C[2,1]=C[1,1]+1，然后按照递归公式走下去。

• C[8, 9] = 5，且$S_1[8] \ne S_2[9]$，所以倒推回去，C[8,9]的值来源于 C[8,8]的值(因为C[8,8] > c[7,9])

• C[8, 8] = 5, 且 $S_1[8] = S_2[8]$, 所以倒推回去，C[8,8]的值来源于 C[7, 7]。

• 可能会出现分歧的情况，$S_1[i] \ne S_2[j]$, 且 C[i-1,j]=C[i, j-1]. 这个时候选择一个方向。

## leetcode 300. Longest increasing sequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

### Dynamic Programming [Accepted]

Optimal Substructure:

Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.

Then, L(i) can be recursively written as:

L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or

L(i) = 1, if no such j exists.

To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.

Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.

Following is a simple recursive implementation of the LIS problem. It follows the recursive structure discussed above.

Time complexity: $O(n^2)$ Two loops of n.

Space complexity: $O(n)$ dp array size n is used.

Xie Pan

2018-12-19

2021-06-29