算法笔记（04）:基础dp

本文参照邓丝雨所写的dp进阶之路所作的笔记，在此%%邓丝雨姐姐

1.介绍

1.1 基本思想

​ dp的核心是对一类求最优解问题的算法，其核心是将一个问题分解成若干个子问题，通过每一次最优决策，求得出一个最优解。

​

1.2 适用条件

三点：

1.具有相同的子问题：首先，我们必须要保证这个问题能够分解出若干个子问题，并且能通过这些子问题来解决这个问题。

2.满足最优化原理（最优子结构）：一个最优决策的子决策也是最优的。

3.具有无后效性：他要求每一个问题的决策，不能对未来问题产生影响，如果产生影响，就无法保证决策的最优性，这就是无后效性。

1.3 解题步骤

1. 确定问题的子问题；

2. 确定状态

3. 推出状态转移方程（关键）

4. 确定边界

5. 优化

1.4 方法

1. 根据dp的三要素，从而确定方向

1.1：先确定阶段的问题 ：数塔问题

1.2 ： 先确定状态的问题 ：常见问题

1.3 ： 先确定决策的问题 ：背包问题

---

2. dp

2.1 线性dp

2.1.1 LIS问题

LIS问题即最长上升子序列（Longest increasing Sequence）：给定一个长为N的数列A，求严格递增的子序列的最长长度是多少？

2.1.1.1 dp，O（n²）解法

首先每个单独的数列是一个子序列，长度为1，因此赋初值f[i]=1；

在此基础上，对i而言，设立一个j从最左扫描到i，去记录每一个比当前值a[i]小的数，通过f[i]来维护当前值。

以 {3 1 2 1 8 5 6}为例子

a[i] 3 1 2 1 8 5 6

len 1 1 2 1 3 3 4

对应的例子是

{3}

{1}

{1,2}

{1}

{1,2,8}

{1,2,5}

{1,2,5,6}

状态转移方程为：

$$\displaystyle dp[j]=\max_{1\leqslant i <j且len(i)<len(j)} dp[i]+1$$

for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

2.1.1.2 贪心+二分 O（nlogn）解法

状态表示：dp[i]表示长度为i的上升子序列的最后一个元素的最小值，类似于维护最值的单调队列。

状态转移：

• 若a[i] > a[len] ,那么dp[++len] = a[i]，即把当前的元素追加到后面，使得上升子序列len+1。
• 2反过来，则在dp中查找大于等于a[i]的第一个数的下标pos，令dp[pos] = a[i]。

最后结果就是dp[len]（最长上升子序列的内容）

int n,dp[N],a[N];
int len=0;
for(int i=1;i<=n;i++)
{
	if(a[i]>a[len]) a[++len] = a[i];
	else
	{
		*lower_bound(dp+1,dp+len+1,a[i])=a[i];
	}
}