数据结构学习day5：递归与动态规划

1 递归与动态规划

1.1 递归

百度百科：程序调用自身的编程技巧称为递归（ recursion）。

递归核心问题：基础部分和递归部分。分析一个递归问题就是列出递归定义表达式的过程。

例子1：斐波那契数列：0，1，1，2，3，5，8，13，21，34，55，89，144……基础部分0，1，递归部分为第3个元素开始为前两个数之和。python递归代码：

def fib(n):
    if n<=1: return n
    return fib(n-2)+fib(n-1)

上述参考：链接1

1.2 动态规划

*：Dynamic programming，是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

所用范围：最优子结构性质、无后效性和子问题重叠性质。

基本思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

核心思想：记忆化存储已经计算过的子问题的解。

动态规划两种形式：1）自顶向下；2）自底向上。(参考链接2)

以例子1分别阐述动态规划的两种形式：首先看递归解决斐波那契数列的过程图：

数据结构学习day5：递归与动态规划

从上图中，发现递归方法计算fib(6)时会计算两次fib(4)，3次fib(3)，5次fib(2)，重复计算使速率减慢。动态规划核心思想即记忆化已经求解的子问题，那么，就可以避免重复计算fib(4),fib(3),fib(2)。

1）自顶向下：解析斐波那契数列：

步骤：a) 设计存储子问题解的list，长度为n+1，转至b);

b) 判断fib(n)是否在list中，若否，转至c)，若存在，直接返回list[n];

c) list[n]=fib(n-1)+fib(n-2)，转至b)；

python demo:

def fib(n, memo=[]):
    memo = [i if n<=1 else -1 for i in range(n+1)]
    if memo[n]!=-1:
        return memo[n]
    else:
        memo[n] = fib(n-1,memo)+fb(n-2,memo)
        return memo[n]

2）自底向上：因需要求解fib(n),不妨一一计算出fib(0),fib(1),fib(2),....,fib(n-1),从来得出fib(n)=fib(n-1)+fib(n-2)

python demo :

def fib(n):
    memo = [i if i<=1 else -1 for i in range(n+1)]
    if n<= 1:
        return memo[n]
    else:
        for i in range(2,n+1):
            memo[i] = memo[i-1]+memo[i-2]
        return memo[n]

简单版：

def fib(n):
    if n <= 1:
        return n
    memo = [0,1]
    for i in range(2,n):
        memo.append(sum(memo[i-2:i]))
    return sum(memo[n-2:n])

1.3 动态规划求解基本步骤

动态规划过程：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来，因此，这种多阶段最优化决策解决问题的过程称为动态规划。

求解的基本步骤：动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些状态形成了一个决策序列，同时确定了完成整个过程的一条活动路线。动态规划的设计一般有如下的几个步骤：

初始状态——>|决策1|——>|决策2|——>...——>|决策n|——>结束状态

步骤：1）划分阶段：根据问题划分为若干个阶段；在划分阶段时，注意划分后的阶段有序或可排序；

2）确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况，用不同状态表示出来；注意，状态的选择要满足无后效性。

3）确定决策并写出状态转移方程：状态转移时根据上一阶段的状态和决策导出本阶段的状态，通常采取根据相邻两个阶段状态之间的关系来确定决策方法和状态转移方程。

4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个地推的终止条件或边界条件。

实际应用中简化步骤：1）分析最优解的性质，刻画其结构特征；

2）递归定义最优解；

3）以自底向上或自顶向下的记忆化方式计算出最优值；

4）根据计算最优值时得到的信息，构造问题的最优解。

（1.3 参考链接3）

2 回顾

hash table: 是根据关键码值(key value)而直接进行访问的数据结构。

单链表：非连续、非顺序的储存结构，由结点构成，每个结点包括数据域和指针域，数据的逻辑顺序由指针链决定。

队列：具有"先进先出"的线性表，有动态和静态两种存储方式。

堆排序：用数组实现的二叉树，根据“堆属性”实现排序。

二叉树：每个结点最多为两个子树的树结构。常见遍历方式：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）、层次遍历。

参考：

链接1：https://blog.csdn.net/qq_34039315/article/details/78679029

链接2：https://blog.csdn.net/u013309870/article/details/75193592

链接3：https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html

数据结构学习day5：递归与动态规划

1 递归与动态规划

2 回顾

相关推荐