DP 动态规划问题
动态规划流程： 暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法
思考流程：找到状态和选择 -> 明确dp数组/函数的定义 -> 寻找状态之间的关系
斐波那契数列优化
if (n == 0 || n == 1)
return n;
else
{
return fib(n - 1) + fib(n - 2);
}
\(时间复杂度 :O(2^n)\) 带备忘录的递归解法
int fibNote(int n)
{
if (!n)
return 0;
vector<int> mem(n + 1, 0);
return note(mem, n);
}
// 备忘录📕
int note(vector<int> &mem, int n)
{
if (n == 1 || n == 2)
return 1;
if (mem[n] != 0)
return mem[n];
mem[n] = note(mem, n - 1) + note(mem, n - 2);
return mem[n];
}
时间复杂度$O(n)$
DP数组的迭代解法
if (n <= 0)
return 0;
vector<int> fb(n + 1, 0);
fb[1] = fb[2] = 1;
for (int i = 3; i < n + 1; i++)
{
fb[i] = fb[i - 2] + fb[i - 1];
}
return fb[n];
状态转移方程 \(\begin{equation} f(n)=\left\{ \begin{array}{cl} 1&n=1,2\\ f(n-1)+f(n-2)&n>2 \\ \end{array} \right. \end{equation}\)
Fibonacci再优化
if (n <= 0)
return 0;
if (n < 3)
return 1;
int pre = 1, cur = 1;
int sum;
for (int i = 3; i < n + 1; i++)
{
sum = pre + cur;
pre = cur;
cur = sum;
}
return sum;
最长公共子序列
LCS - Longest Common Subsequence
input: str1 = “abcde”, str2 = “ace”
output: 3
-
Step 1 明确dp数组的含义
$dp[i][j]$代表$s_1[1…i]$和$s_2[1…j]$的公共子序列
-
定义 base case 起始
$dp[0][…]\&dp[…][0]=0$
-
状态转移方程
用两个指针 i 和 j 从后往前遍历 s1 和 s2 ，如果 s1[i]==s2[j] ，那 么这个字符一定在 lcs 中;否则的话， s1[i] 和 s2[j] 这两个字符至少 有一个不在 lcs 中，需要丢弃一个。 \(\begin{equation} c(n)=\left\{ \begin{array}{cl} 0 & i>0;j=0\\ c[i-1][j-1]+1&i,j>0;x_i=y_i\\ max\{c[i][j-1],c[i-1][j]\}&i,j>0;x_i!=y_i \end{array} \right. \end{equation}\)
