东营网站推广公司,做网站1g1核够吗,高端猎头公司排名,做书的封面的网站素材动态规划
动态规划#xff08;DP#xff09;是一种对问题的状态空间进行分阶段、有顺序、不重复、决策性遍历的算法。关键与前提 重叠子问题#xff1a;与递归、分治等一样#xff0c;要具有同类子问题#xff0c;用若干维状态表示。最优子结构#xff1a;状态对应着一个…动态规划
动态规划DP是一种对问题的状态空间进行分阶段、有顺序、不重复、决策性遍历的算法。关键与前提 重叠子问题与递归、分治等一样要具有同类子问题用若干维状态表示。最优子结构状态对应着一个最优化目标并且最优化目标之间具有推导关系。无后效性问题的状态空间是一张有向无环图可按一定的顺序遍历求解动态规划一般采用递推的方式实现可以写成递归或搜索的形式因为每个状态只遍历一遍也被称为记忆化搜索。 动态规划三要素阶段线性增长、状态具有最优子结构、决策找到子问题。动态规划打印方案记录转移路径 递归输出 动态规划选取 “代表”维护了一个最优子结构。如果记录每个最优子结构的详细方案时间复杂度会上升。 动态规划模版// 0. Move index to 1-based
// 1. Define f, initialize
// 2. Loop over all states
// 3. Copy decisions
// 4. return target
int maxProfit(vectorint prices) {int n prices.size();// 0. move index to 1-basedprices.insert(prices.begin(), 0);// 1. define f, initvectorvectorint f(n 1, vectorint(2, -1e9));f[0][0] 0;// 2. loop all statesfor (int i 1; i n; i) {// 3. copy decisionsf[i][1] max(f[i][1], f[i - 1][0] - prices[i]);f[i][0] max(f[i][0], f[i - 1][1] prices[i]);for (int j 0; j 2; j) {f[i][j] max(f[i][j], f[i - 1][j]);}}// 4. return targetreturn f[n][0];
}LeetCode 练习题
322. 零钱兑换62. 不同路径63. 不同路径 II1143. 最长公共子序列300. 最长递增子序列53. 最大子数组和152. 乘积最大子数组70. 爬楼梯120. 三角形最小路径和673. 最长递增子序列的个数121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III188. 买卖股票的最佳时机 IV714. 买卖股票的最佳时机含手续费309. 买卖股票的最佳时机含冷冻期198. 打家劫舍213. 打家劫舍 II72. 编辑距离 背包问题
0/1 背包 给定 N 个物品其中第 i i i 个物品的体积为 V i V_i Vi价值为 W i W_i Wi。 有一容积为 M M M 的背包要求选择一些物品放入背包使得物品总体积不超过 M M M 的前提下物品的价值总和最大。 F [ i , j ] 表示从前 i 个物品中选出了总体积为 j 的物品放入背包物品的最大价值和 F[i, j] 表示从前 \ i \ 个物品中选出了总体积为 \ j \ 的物品放入背包物品的最大价值和 F[i,j]表示从前 i 个物品中选出了总体积为 j 的物品放入背包物品的最大价值和 F [ i , j ] m a x { F [ i − 1 , j ] 不选第 i 个物品 F [ i − 1 , j − V i ] W i i f j ≥ V i 选第 i 个物品 F[i, j] max\left\{ \begin{aligned} F[i-1,j] \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \ \ \ \ \ \ 不选第 \ i \ 个物品 \\ F[i-1,j-V_i] W_i \quad\quad if\quad j\geq V_i \quad\quad选第 \ i \ 个物品 \end{aligned} \right. F[i,j]max{F[i−1,j] 不选第 i 个物品F[i−1,j−Vi]Wiifj≥Vi选第 i 个物品初值 F [ 0 , 0 ] 0 F[0,0] 0 F[0,0]0其余为负无穷目标 max 0 ≤ j ≤ M { F [ N ] [ j ] } \max_{0 \leq j \leq M} \left\{ F[N][j] \right\} max0≤j≤M{F[N][j]} vectorvectorint f(n 1, vectorint(m 1, -1e9));
f[0][0] 0;for (int i 1;i n;i) {for (int j 0;j m;j) {f[i][j] f[i - 1][j];}for(int j v[i];j m;j) {f[i][j] max(f[i][j], f[i - 1][j - v[i]] w[i]);}
}int ans 0;
for (int j 0;j m;j) ans max(ans, f[n][j]);vectorint f(m 1, -1e9);
f[0] 0;for (int i 1;i n;i)for (int j m;j v[i];j--) // 必须倒序f[j] max(f[j], f[j - v[i]] w[i]);int ans 0;
for (int j 0;j m;j) ans max(ans, f[j]);LeetCode 练习题
416. 分割等和子集494. 目标和 完全背包 给定 N 种物品其中第 i i i 种物品的体积为 V i V_i Vi价值为 W i W_i Wi并且有无数个。 有一容积为 M M M 的背包要求选择一些物品放入背包使得物品总体积不超过 M M M 的前提下物品的价值总和最大。 F [ i , j ] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包物品的最大价值和 F[i, j] 表示从前 \ i \ 种物品中选出了总体积为 \ j \ 的物品放入背包物品的最大价值和 F[i,j]表示从前 i 种物品中选出了总体积为 j 的物品放入背包物品的最大价值和 F [ i , j ] m a x { F [ i − 1 , j ] 尚未选过第 i 种物品 F [ i , j − V i ] W i i f j ≥ V i 从第 i 种物品中选一个 F[i, j] max\left\{ \begin{aligned} F[i-1,j] \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \ \ \ 尚未选过第 \ i \ 种物品 \\ F[i,j-V_i] W_i \quad\quad if\quad j\geq V_i \quad\quad\quad\quad从第 \ i \ 种物品中选一个 \end{aligned} \right. F[i,j]max{F[i−1,j] 尚未选过第 i 种物品F[i,j−Vi]Wiifj≥Vi从第 i 种物品中选一个初值 F [ 0 , 0 ] 0 F[0,0] 0 F[0,0]0其余为负无穷目标 max 0 ≤ j ≤ M { F [ N ] [ j ] } \max_{0 \leq j \leq M} \left\{ F[N][j] \right\} max0≤j≤M{F[N][j]} vectorint f(m 1, -1e9);
f[0] 0;for (int i 1;i n;i)for (int j v[i];j m;j) // 正序f[j] max(f[j], f[j - v[i]] w[i]);int ans 0;
for (int j 0;j m;j) ans max(ans, f[j]);LeetCode 练习题
322. 零钱兑换518. 零钱兑换 II279. 完全平方数55. 跳跃游戏 区间动态规划
区间动态规划的子问题是基于一个区间的。区间长度作为 D P DP DP 的 “阶段”区间端点作为 D P DP DP 的 “状态”。在计算区间长度为 l e n len len 的子问题时要先算好所有长度 l e n len len 的子问题。 LeetCode 练习题
312. 戳气球516. 最长回文子序列 树形动态规划
是套在深度优先遍历里的动态规划在 D F S DFS DFS 的过程中实现 D P DP DP子问题就是 “一棵子树”状态一般表示为 “以 x x x 为根的子树”决策就是 “ x x x 的子节点”。 LeetCode 练习题
337. 打家劫舍 III124. 二叉树中的最大路径和
