minux_sufe
minux_sufe
全部文章
算法
题解(28)
归档
标签
去牛客网
登录
/
注册
Code Rush
0x00
全部文章
/ 算法
(共2篇)
区间DP (2)
问题链接: 能量项链 思路: 区间DP 环形区间展开为链式区间, 定义f[i][j]表示区间[i,j]的能量转移方程为f[i][j]=f[i][k]+f[k][j]+a[i]*a[k]*a[j] 算法设计 python from typing import List class Solution: ...
动态规划
2020-05-14
0
482
区间DP (1)
问题链接: 环形石子合并 思路: 区间DP 区间处理题目中给出了一个环状区间, 如果考虑贪心算法, 可以找到反例; 如果对区间缺口进行枚举, 那么时间复杂度为.一种常用的优化技巧为复制一倍区间, 将环状区间转为链式区间存储, 枚举长度为的区间, 优化后的时间复杂度为. 动态规划状态定义: f[l]...
动态规划
前缀和
2020-05-14
0
500