tonngw

分类

题解(12)

/ 注册

全部文章（共4篇）

题解 | #打家劫舍(二)#

动态规划相同的代码跑两遍，和（一）思路一样 f[i] 表示偷第 i 个房间，g[i] 表示不偷第 i 个房间这里分两种情况：不选起点，答案就是 res = max(f[n], g[n]) 最大值选起点，那么就不能选终点，所以答案就是 res = max(res, g[n]) cl...

C++ 动态规划

2022-03-08

0 358

题解 | #环形数组的连续子数组最大和#

(动态规划) O(n)O(n)O(n) 这道题目是 NC19 连续子数组的最大和的升级版，增加了环形情况。分两种情况考虑问题：无环情况下：求出连续子数组的最大值 res 有环情况下：先求出无环情况下连续子数组的最小值 res2，然后用数组和 sum 减去最小值 res2 即为环形情况...

C++ 动态规划

2022-03-05

2 641

题解 | #最长上升子序列(三)#

算法 1 (动态规划) O(n)O(n)O(n) 状态表示：f[i]f[i]f[i]，表示以 arr[i] 结尾的最大上升子序列的长度。状态计算：f[i]=max(f[i],f[j]+1),j∈[0,i−1]f[i] = max(f[i], f[j] + 1), j \in [0, i - 1]...

C++ 动态规划二分查找贪心

2022-02-27

0 468

题解 | #最长上升子序列(三)#

(动态规划) O(n)O(n)O(n) 状态表示：f[i]f[i]f[i]，表示以 arr[i] 结尾的最大上升子序列的长度。状态计算：f[i]=max(f[i],f[j]+1),j∈[0,i−1]f[i] = max(f[i], f[j] + 1), j \in [0, i - 1]f[i]=...

C++ 动态规划二分查找贪心

2022-02-27

0 350