算法设计与分析dp算法

### 动态规划算法设计与分析

#### 定义与本质
动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。这种技术主要应用于优化问题，在这些问题中，目标是最小化或最大化某个量[^1]。

#### 特点概述
该方法具有两个显著特点：重叠子问题和最优子结构性质。当一个问题可以被划分为若干个重复出现的小规模相同问题时，则认为存在重叠子问题；而如果一个问题的整体最优解可以通过其各个部分的局部最优解组合得到的话，则说明此问题是具备最优子结构特性的。

#### 解题思路框架
对于采用动态规划来解决问题而言，通常会遵循以下几个方面思考：

- **定义状态**：确定如何表示每一个阶段的状态以及这些状态之间的关系。

- **建立转移方程**：基于所选状态表达方式推导出从前一个状态转移到当前状态所需的条件公式。

- **初始化边界条件**：设定初始时刻各变量的具体数值以便于后续迭代计算过程顺利开展。

- **执行顺序安排**：按照一定规律依次处理不同时间点上的事件直至完成整个流程。

- **返回最终结果**：经过一系列运算操作之后得出满足题目要求的答案形式并输出给用户查看。

#### 应用场景举例
一些典型的应用实例包括但不限于以下几种情况：

- 斐波那契数列：这是一个经典的例子，其中每一项都等于前两项之和；

- 连续子数组最大和：寻找一段序列里连续元素构成的新列表使得它们加起来总值尽可能大；

- 公共子串匹配：判断两段文字间是否存在共同拥有的片段，并找出最长的那个；

- 字符串分割（Word Break）：验证能否将一句话拆分成字典中存在的单词集合；

- 通配符模式识别：支持问号`?`代表任意单字符星号`*`代替零个或多个未知符号的功能实现。

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    elif n <= 2:
        f = 1
    else:
        f = fib(n - 1, memo) + fib(n - 2, memo)
    memo[n] = f
    return f


def max_subarray(nums):
    dp = [0]*len(nums)
    dp[0], res = nums[0], nums[0]

    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        res = max(res, dp[i])

    return res