1. 最长上升子序列

Leetcode-300-mid-最长上升子序列

数组存储信息含义：

arr[i] 存储以第i个数字结尾的最长上升序列的长度f(i)。

转移关系

使用递推的思考还是归纳式的思考比较好？

若序列 s s s以第k+1个数字结尾的话，目前已有arr[0]、arr[1]、…、arr[k];
arr[k+1]的计算：将nums[k+1]放在以nums[j]结尾的最长上升序列后，其中需要满足( j ≤ k 且 n u m s [ j ] ≤ n u m s [ k + 1 ] j\leq k 且 nums[j] \leq nums[k+1] j≤k且nums[j]≤nums[k+1])，所得到的以nums[k+1]结尾的最长上升序列。

迭代更新公式

f ( i ) = { 1 i = 0 m a x ( f ( 0 ) , f ( 1 ) , . . . , f ( j ) , . . . , f ( i − 1 ) ) + 1 n u m s [ j ] < n u m s [ i ] f(i) = \begin{cases} 1 & i=0 \\ max( f(0), f(1), ..., f(j), ..., f(i-1))+1 & nums[j]<nums[i] \end{cases} f(i)={1max(f(0),f(1),...,f(j),...,f(i−1))+1​i=0nums[j]<nums[i]​

2. 最长公共子序列

LeetCode-1143-mid-最长公共子序列

数组存储信息含义：

arr[i][j] 存储第一个文本的前i个字符与第二个文本的前j个字符(两个子串)的最长公共子序列

转移关系

也可以根据最后一个字符是否在公共子串中进行分类。

已有题解的描述

对于arr[m] [n],比较str1[m]与str2[n]是否相同:
如果相同，则查看第一个文本的前m-1个字符和第二个文本的前n-1个字符的最长公共子序列。$arr[m] [n] = arr[m-1] [n-1]+1 $
如果不同，则查看第一个文本的前m个字符和第二个文本的前n-1个字符的最长公共子序列 与 则查看第一个文本的前m-1个字符和第二个文本的前n个字符的最长公共子序列；选择两者中的大的。$arr[m] [n] = max( arr[m-1] [n], arr[m] [n-1] ) $

实际思考上的分析

设最长公共子串为s，根据str2[n]是否在s中分为两种情况考虑。

• 如果str2[n]不在s中，则最长公共子串也是(str1, str2[:n-1])的最长公共子串

• 如果str2[n]在s中，在str1从后向前找到等于str2[n]的字符：但是需要查找的复杂度。

  如果str1[m] ==str2[n]，则查找 (str1[:m-1], str2[:n-1])的最长公共子串，并附加上该字符

  如果str1[m]!=str2[n]，则查找（str1[m-1], str2[n])的最长公共子串

可以分析知道，如果情况1成立，则一定有str1[m] != str2[n];

整理后为题解的表述。

迭代更新公式

f ( m , n ) = { 0 m = 0 或 n = 0 f ( m − 1 , n − 1 ) + 1 s t r 1 [ m ] = s t r 2 [ n ] m a x ( f ( m − 1 , n ) , f ( m , n − 1 ) ) s t r 1 [ m ] ≠ s t r 2 [ n ] f(m,n) = \begin{cases} 0 & m=0或n=0 \\ f(m-1,n-1)+1 & str1[m]=str2[n] \\ max( f(m-1,n), f(m,n-1) ) & str1[m]\neq str2[n] \end{cases} f(m,n)=⎩⎪⎨⎪⎧​0f(m−1,n−1)+1max(f(m−1,n),f(m,n−1))​m=0或n=0str1[m]=str2[n]str1[m]​=str2[n]​

相关问题

• 最长公共子序列的个数？
• 有哪些最长公共子序列（字符串）
• 如果是三个字符串呢？

3. 爬楼梯

LeetCode-746-easy-使用最小花费爬楼梯

经典动态规划

数组存储信息含义：

MinCost[i]存储爬到第i阶楼梯的最小花费。

转移关系

爬到第i个楼梯所需要的花费是前两个楼梯的最小花费+当前楼梯所需要的花费

迭代更新公式

M i n C o s t [ i ] = M i n ( M i n C o s t [ i − 1 ] , M i n C o s t [ i − 2 ] ) + c o s t [ i ] MinCost[i] = Min(MinCost[i-1],MinCost[i-2])+cost[i] MinCost[i]=Min(MinCost[i−1],MinCost[i−2])+cost[i]

M i n C o s t [ i ] = { c o s t [ i ] i = 0 , 1 m i n ( M i n C o s t [ i − 1 ] , M i n C o s t [ i − 2 ] ) + c o s t [ i ] i ≥ 2 MinCost[i] = \begin{cases} cost[i] & i=0,1 \\ min(MinCost[i-1], MinCost[i-2])+cost[i] & i \ge 2 \end{cases} MinCost[i]={cost[i]min(MinCost[i−1],MinCost[i−2])+cost[i]​i=0,1i≥2​

4. 模：购物列表

0-1 背包

购物列表中每个物品是否购买，共有2^n种组合

每个物品作为外循环，不断更新dp

数组存储信息含义：

dp[i] : 对于前k个物品，加个取模为i 对应的最大金额数。

dp[1]: 对于前k个物品，买或不买，总金额取模后余1的最大金额数。

转移关系：

对于当前遍历物品k+1, 价格为 w k + 1 w_{k+1} wk+1​

n e x t _ d p [ i ] = m a x ( d p [ i ] , d p [ M O D − w k + 1 % M O D ] + w k + 1 ) next\_dp[i] = max( dp[i], dp[ MOD-w_{k+1}\% MOD] + w_{k+1} ) next_dp[i]=max(dp[i],dp[MOD−wk+1​%MOD]+wk+1​)

其中 n e x t _ d p [ i ] next\_dp[i] next_dp[i]表示前k+1个物品对应，总金额取模后为i的最大金额数

5. 有限人数：执行任务选择，获取利益

0-1 背包

根据每个人数是否执行，共有2^n种组合方式。

每个任务作为外循环，不断更新dp

数组存储信息含义：

dp[i][j] 使用i个人，获得收益j的种数

dp[0][0] 取1 没人干活取得0收益；部分位置为不存在或不合理，取0

转移关系：

输入：pre[i][j] 和 新任务( 需要m人，产生n利益 )

输出：curr[i][j]

c u r r [ i ] [ j ] = p r e [ i − m ] [ j − n ] + p r e [ i ] [ j ] curr[i][j] = pre[i-m][j-n] + pre[i][j] curr[i][j]=pre[i−m][j−n]+pre[i][j]

可能会要求取模；

根据问题约束条件的个数来确定dp使用存储数据的矩阵维度