分治思想和解决冗余
dp和分治的区别:
动态规划
- 子问题重叠：动态规划适用于子问题有大量重叠的情况。在动态规划中，每个子问题只解决一次，其解决方案被保存在表格中（通常是数组或字典），以便以后可以直接使用，避免了重复计算。
- 最优子结构：动态规划要求原问题具有最优子结构特性，即原问题的最优解可以由子问题的最优解有效地构建出来。
- 记忆化：动态规划通常使用记忆化技术（存储子问题的解），这是它与纯粹分治算法的一个关键区别。
- 自底向上或自顶向下：动态规划可以自底向上（从最小的子问题开始解决，逐步构建到整个问题的解决方案），或自顶向下（先解决大问题，再递归地解决子问题）。
分治算法
- 子问题独立：分治算法适用于子问题是独立的情况，即子问题之间没有重叠。每个子问题都是新的问题，需要独立计算。
- 递归分解：分治算法通常通过递归地将问题分解成两个或多个较小的子问题，直到子问题足够小，可以直接求解。
- 组合子问题的解：在分治算法中，子问题的解被合并或“组合”起来以构成原问题的解。
- 不涉及记忆化：由于子问题是独立的，分治算法通常不存储子问题的解，因此不涉及记忆化技术。
dp和greedy区别:
-
在动态规划方法中，每个步骤也都要进行一次选择，但这种选择通常依赖于子问题的解。因此，通常以自底向上地方式求解动态规划问题，先求解较小的子问题，然后才能求解较大的子问题
-
在贪心算法中，我们总是做出当前看来最佳的选择，然后求解剩下的唯一一个子问题。贪心算法进行选择时可能依赖之前做出的选择，但不依赖任何将来的选择或子问题的解
-
动态规划要先求解子问题才能进行第一次选择，贪心算法在进行第一次选择之前不需要求解任何子问题
-
动态规划算法通常采用自底向上的方式完成计算，而贪心算法通常是自顶向下的，每一次选择，将给定问题实例转换成更小的问题
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1] 输出：1示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
分治解法:
class Solution {
public:
int FindMaxCrossingSubarry(const vector<int> &v,int low,int mid,int high){
int left_sum = INT_MIN; //初始化最小值
int sum_l = 0; //sum用来存放总和
for(int i = mid; i >= low; i--)
{
sum_l += v[i];
if(sum_l > left_sum)
{
left_sum = sum_l;
}
}
int right_sum = INT_MIN;
int sum_r = 0;
for(int j = mid + 1; j <= high; j++)
{
sum_r+=v[j];
if(sum_r > right_sum)
{
right_sum = sum_r;
}
}
return left_sum+right_sum;
}
int FindMaxSubarry(const vector<int> &v, int low, int high){
if(low == high)
{
return v[low];
}
int mid = (low + high)/2;
int left_sum = FindMaxSubarry(v, low, mid);
int right_sum = FindMaxSubarry(v, mid + 1, high);
int cross_sum = FindMaxCrossingSubarry(v, low, mid, high);
if(left_sum >= right_sum && left_sum >= cross_sum)
{
return left_sum;
}
else if(right_sum >= left_sum && right_sum >= cross_sum)
{
return right_sum;
}
else
{
return cross_sum;
}
}
int maxSubArray(vector<int>& nums) {
return FindMaxSubarry(nums, 0, nums.size() - 1);
}
};dp解法:
最终结果为$dp$数组中最大的一个
关键词:
- 无后效性:在给定当前的状态和的决策（动作）下，系统的下一个状态仅取决于当前状态和决策，并且与如何达到当前状态或未来决策无关
- 最优子结构:一个问题的最优解一定包含其子问题的最优解
- 重叠子问题:即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题(与分治策略的不同)
给定两个字符串
text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在公共子序列 ，返回0。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
构建二维$dp$数组,其中$dp[i][j]$表示$text_1[0:i]$与$text_2[0:j]$中的公共子序列的长度
状态转移方程:
$$
dp[i][j] =
\begin{cases}
0 & i = 0\ or\ j = 0 \
dp[i - 1][j - 1] + 1 & text_1[i - 1] = text_2[j - 1] \
max(dp[i - 1][j], dp[i][j - 1]) & text_1[i - 1] \neq text_2[j - 1]
\end{cases}
$$
- 当
$i = 0$ 时,$text_1[0:i]$为空,因此$text_1[0:i]与text_2[0:j]$的公共子序列长度一定为0,$dp[0][j] = 0$ - 当$j = 0$时,同理可得$dp[i][0] = 0$
0-1 背包问题和分数背包问题：都具有最优子结构性质
-
0-1 背包问题：动态规划算法
-
分数背包问题：贪心算法，按
$\frac{p_i}{v_i}$ 的降序考虑问题
给定物品价值与体积（对应了「给定价值与成本」），在规定容量下（对应了「限定决策规则」）如何使得所选物品的总价值最大。
有$N$件物品和一个容量是$V$的背包。每件物品有且只有一件。
第$i$件物品的体积是$v[i]$，价值是$w[i]$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
对于第$i$件物品有两个选择:拿或不拿
拿:此时$dp[i][c]$表示的为$考虑前i件物品，使用容量不超过c$,但是由于第$i$件物品没有拿,因此与$考虑前i - 1件物品，使用容量不超过c$一样,即$dp[i][c] = dp[i - 1][c]$
不拿:此时在拿了第$i$件物品后,背包的容量减少了$v[i]$,但是背包的价值增加了$w[i]$,即$dp[i][c] = dp[i - 1][c - w[i]] + v[i]$
两者取大的,最终的状态转移方程: $$ dp[i][c] = \begin{cases} max(dp[i - 1][c], dp[i - 1][c - w[i]] + v[i]) & 0 \leq w[i] \leq c\ dp[i - 1][c] & w[i] \geq c\ \nonumber \end{cases} $$
一维空间优化:
PPT例题:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 重量$w$ | 2 | 1 | 3 | 2 |
| 价值$v$ | 12 | 10 | 20 | 15 |
计算出的dp表格:
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 12 | 12 | 12 | 12 |
| 2 | 0 | 10 | 12 | 22 | 22 | 22 |
| 3 | 0 | 10 | 12 | 22 | 30 | 32 |
| 4 | 0 | 10 | 15 | 25 | 30 | 37 |
最终计算出的$dp[4][5] = 37$,即对于前4个物品,当背包容量为5时,可以装下的物品的最大价值为37
==注意:PPT上的表格的状态状态转移方程是从后向前计算的,导致表格不同==
有$N$件物品和一个容量是$V$的背包。每件物品有无数件。
第$i$件物品的体积是$v[i]$，价值是$w[i]$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
给你一个整数数组
coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回
-1。你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1示例 2：
输入：coins = [2], amount = 3 输出：-1示例 3：
输入：coins = [1], amount = 0 输出：0
与传统的完全背包问题不同，这里的目标是最小化硬币数量，而不是最大化价值。
dp:
对于第$i$个硬币,可以选,也可以不选择
不选:$dp[i][j] = dp[i - 1][j]$
选:$dp[i][j] = dp[i][j - coin[i]] + 1$(最优子结构)
因此状态转移方程为$dp[i][j] = min(dp[i - 1][j], dp[i][j - coin[i]] + 1)$
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n: int = len(coins)
@cache
def dfs(i: int, j: int) -> int:
if j < 0:
return amount + 1
if j == 0:
return 0
if i == 0:
return amount + 1
return min(dfs(i - 1, j), dfs(i, j - coins[i - 1]) + 1)
ans: int = dfs(n, amount)
if ans == amount + 1:
return -1
return ans 空间压缩:
给你一个整数
n，返回 和为n的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，
1、4、9和16都是完全平方数，而3和11不是。示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
二维dp:
这道题中相当于每个元素的$v[i] = 1, w[i] = i^2$
class Solution:
def numSquares(self, n: int) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i <= 0:
return inf
if j == 0:
return 0
if j < 0:
return inf
return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)
return dfs(int(n ** 0.5), n)class Solution {
public:
int numSquares(int n) {
int m = sqrt(n);
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
for(int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if (i * i <= j) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - i * i] + 1);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
};假设需要凑出的数为20,dp数组中的内容:
下面是这个二维dp数组的值（dp[i][j] 表示使用前 i 个数凑出 j 所需的最小数的个数）：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 2 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 3 | 4 | 5 | 3 | 4 | 5 | 6 | 4 | 5 | 6 | 7 | 5 |
| 3 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 1 | 2 | 3 | 3 | 2 | 3 | 4 | 4 | 3 | 2 | 3 | 4 |
| 4 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 1 | 2 | 3 | 3 | 2 | 3 | 4 | 1 | 2 | 2 | 3 | 2 |
在这个表格中，"∞" 代表无穷大，意味着无法用前 i 个数来凑出 j。例如，dp[4][20] = 2 表示使用前4个数（即1, 4, 9, 16）凑出20所需的最小数的个数是2（例如，4和16）。
最终$dp[4][20] = 2$,代表为了凑出20,至少需要两个数
空间压缩?
第$i$种钢条的长度为$length[i]$,价值为$price[i]$
书上多做了一步状态压缩的过程
可以理解为完全背包问题,$dp[i][j]$指选择前$i$种长度的钢条,总长度为$j$,此时的最大价值
空间压缩后:
这道例题中恰好$length[i] = i$
/*
* @param n: 钢条总长度
* @param p: 钢条长度对应的价格
* @return: 钢条最大收益
* @description: 自底向上的动态规划,一维动态规划
*/
int OneDimensionalDP(const int n, const std::vector<int>&p) {
std::vector<int> dp(n + 1, 0);
for(int i = 0; i <= n; i++){
for(int j = 0; j <= i; j++){
dp[i] = std::max(dp[i], p[j] + dp[i - j]);
}
}
return dp[n];
}
/*
* @param n: 钢条总长度
* @param p: 钢条长度对应的价格
* @return: 钢条最大收益
* @description: 自底向上的动态规划,二维动态规划
*/
int TwoDimensionalDP(const int n, const std::vector<int>& p) {
const int size = static_cast<int>(p.size());
std::vector<std::vector<int>> dp(size, std::vector<int>(n + 1, 0));
for(int i = 1; i < size; i++){
for(int j = 0; j <= n; j++) {
if(i <= j){
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - i] + p[i]);
}else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[size - 1][n];
}
PPT例题:
给定三个物品(物品可以切割),背包大小20,$v = {25, 24, 15}$,$w = {18, 15, 10}$
| 1 | 2 | 3 | |
|---|---|---|---|
| 25 | 24 | 15 | |
| 18 | 15 | 10 | |
| 1.389 | 1.6 | 1.5 |
因此先把2拿光,在尽可能多的拿3
书上P255
a.总是优先选择最高面额的硬币
b.给定一个最优解
c.硬币为1,3,4,需要找6,此时贪心算法为4,1,1,最优解为3,3
d.见上面的dp中的硬币兑换
正确性:
定理:考虑任何非空子问题$S_k$,令$a_m$是$S_k$中结束时间最早的活动,则$a_m$在$S_k$的某个最大兼容活动子集中
令$A_k$是$S_k$中的一个最大兼容子集,且$a_j$是$A_k$中结束时间最早的活动.
若$a_j = a_m$,则已经证明$a_m$在$S_k$的某个最大兼容活动子集中.
若$a_j \neq a_m$,令集合$A'_k = A_k - {a_j} \cup {a_m}$,即将$A_k$中的$a_j$替换为$a_m$,$A'_k$中的活动都是不相交的,因为$A_k$中的活动都是不相交的,$a_j$是$A_k$中结束时间最早的活动,而$f_m \leq f_j$.由于$|A'_k| = |A_k|$,因此得出结论$A'_k$也是$S_k$的一个最大兼容子集,且它包括$a_m$