今天复习一下拓扑排序

来提每日一题 2024-07-22 12:22:11
校招找工作实录 转码 每日一题 北美求职 LeetCode 每天59秒拿下每日一题 近期找工作现状 国区每日一题今日思路: 动态规划。分为删除和保留当前元素,记dp0为无法再删除元素,dp1为可以删除1位。初始值dp0=0, dp1=arr[0],状态转移方程有dp0=max(dp0 + arr[i], dp1),dp1=max(0, dp1) + arr[i],这里根据前缀和决定是否保留之前元素,维护dp的全局最优为答案。 国际站每日一题今日思路: 拓扑排序。分别按行和列进行拓扑排序,对于所给顺序,从第一个元素添加一条到第二个元素的边,进行拓扑排序;若存在环直接返回空矩阵;否则一定可以根据所得拓扑排序生成矩阵。看到这点个赞吧[喝奶茶R]
0 阅读:0