Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。🌈个人主页：主页链接🌈算法专栏：专栏链接 我会一直往里填充内容哒！🌈LeetCode专栏：专栏链接 目前在刷初级算法的LeetBook。若每日一题当中有力所能及的题目，也会当天做完发出🌈代码仓库：Gitee链接🌈点击关注=收获更多优质内容🌈目录题目:戳气球题解:代码实现:完结撒花因为一些事,最近状态不是很好,加上今天的每日一题有点难,看的烦躁(就是菜,就来更新一下今天与每日一题相关的区间Dp问题(戳气球),这篇也是关于区间Dp的问题uu可以看看 话不多说,开始! 题
【LetMeFly】1824.最少侧跳次数力扣题目链接：https://leetcode.cn/problems/minimum-sideway-jumps/给你一个长度为 n 的 3跑道道路 ，它总共包含 n+1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。给你一个长度为n+1 的数组 obstacles ，其中 obstacles[i] （取值范围从0到3）表示在点i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i]==0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个
尝试为一般硬币找零问题编写DP解决方案，同时跟踪使用了哪些硬币。到目前为止，我一直在努力为我提供所需的最少硬币数量，但无法弄清楚如何获得使用了哪些硬币以及使用了多少次。如果使用硬币，我尝试用值设置另一个表(boolean值)，但这似乎无法正常工作。有什么想法吗？publicstaticintminChange(int[]denom,intchangeAmount){intm=denom.length;intn=changeAmount+1;int[][]table=newint[m][n];boolean[][]used=newboolean[m][n];for(intj=0;j=0;
原题链接https://pintia.cn/problem-sets/994805046380707840/exam/problems/1649748772845703169题目大意给定一棵有NNN个结点的树（树中结点从111到NNN编号，根结点编号为111）。每个结点有一种颜色，或为黑，或为白。若子树中黑色结点与白色结点的数量之差的绝对值不超过111，称以结点uuu为根的子树是好的。若对于所有1≤i≤N1≤i≤N1≤i≤N，以结点iii为根的子树都是好的，称整棵树是完美树。你需要将整棵树变成完美树，为此你可以进行以下操作任意次（包括零次）：选择任意一个结点iii(1≤i≤N)(1≤i≤N)(
动态规划（DP）：是运筹学的一个分支，是求解决策过程最优化的过程适用场景：用于求解具有某种最优性质的问题闫式分析法基本思想：将待求解问题分解成若干个子问题，求解子问题的数学关系式，然后从这些子问题的关系式拼接成原问题的解法，然后将问题的条件从低到题目条件分层计算，需要注意的是经过分层得到的答案往往不是互相独立的，保存已解决的低层答案，在计算下一层或高层数据结果时再找出已求得的答案用以避免大量的重复计算，节省时间优化方向：DP的所有优化都是对代码的等形变换，它和题目无关，和代码的逻辑有关代码编写：使用DP应该是使用循环，将运算过程逐渐算出，即层次计算，先计算出底层的数据然后存储，在计算高层数据时
小美的平衡矩阵写在前面:本博客只是一种解题思路的提供。小美的平衡矩阵题目描述：小美拿到了一个n*n的矩阵，其中每个元素是0或者1。小美认为一个矩形区域是完美的，当且仅当该区域内0的数量恰好等于1的数量。现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答1输入描述第一行输入一个正整数n，代表矩阵大小。接下来的n行，每行输入一个长度为n的01串，用来表示矩阵。输出描述输出n行，第i行输出的I*I完美矩形区域的数量。示例1输入41010010111000011输出0701思路：符合条件的矩阵的边一定是偶数，只有偶数才能保证0和1的数量相等确定一个矩阵只需要确定这个矩阵的四个顶点中的一个和边
1、B站视频链接：E28【模板】区间DP石子合并_哔哩哔哩_bilibili题目链接：石子合并（弱化版）-洛谷#includeusingnamespacestd;constintN=310;intn,a[N],s[N];intf[N][N];//f[i][j]表示从i到j合并成一堆的最小代价intmain(){ memset(f,0x3f,sizeof(f)); cin>>n; //预处理 for(inti=1;i>a[i],s[i]=s[i-1]+a[i],f[i][i]=0; } //状态计算 for(intlen=2;len2、B站视频链接：E29区间DP环形石子合并_哔哩哔哩_bili
以经典问题“打家劫舍”来解释简单多状态dp问题和解决方法打家劫舍I题目链接：打家劫舍I这种问题就是在某一个位置有多个状态可以选择，选择不同的状态会影响最终结果在这道题中就是小偷在每一个房屋，可以选择偷或不偷，每一次选择都会影响最终偷窃金额状态表示因为每一步都有两个状态，所以我们要用两张dp表来表示，分别记为f和g，f[i]表示从开始到第i号房屋，偷窃第i号房屋可获得的最大金额；g[i[则表示不偷第i号房屋可获得的最大金额状态转移方程推导转移方程常用的策略就是找最近的一步，离f[i]最近的一步就是i-1，而偷了第i号房屋就意味着第i-1号不能偷，也就是g[i-1]+nums[i]而对于g[i]，
目录DP分析：优化： 二进制优化例题： 01背包是每个物品只有一个，完全背包问题是每个物品有无限个。 那么多重背包问题就是每个物品有有限个。有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。DP分析： 和完全背包问题很像，暴力算法都是多加一层循环，循环物品的个数。O(n^3)动态规划DP之背包问题2---完全背包问题-CSDN博客 实现代码：for(inti=1;i优化： 不能采用完全背包的优化方式。动态规划DP之背包问题2
五部曲（代码随想录）1.确定dp数组以及下标含义2.确定递推公式3.确定dp数组初始化4.确定遍历顺序5.debug入门题1.斐波那契数思路1.f[i]：第i个数的值2.f[i]=f[i-1]+f[i-2]3.f[0]=0,f[1]=14.顺序遍历5.记得特判n==0的时候，因为初始化了f[1]classSolution{public:intfib(intn){if(n==0)returnn;vectorint>f(n+1);f[0]=0,f[1]=1;for(inti=2;in;i++)f[i]=f[i-1]+f[i-2];returnf[n];}};2.爬楼梯思路每次可以从下面一个台阶或者
