minux_sufe

算法

题解(28)

/ 注册

全部文章 / 算法（共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 485

区间DP (1)

问题链接: 环形石子合并思路: 区间DP 区间处理题目中给出了一个环状区间, 如果考虑贪心算法, 可以找到反例; 如果对区间缺口进行枚举, 那么时间复杂度为.一种常用的优化技巧为复制一倍区间, 将环状区间转为链式区间存储, 枚举长度为的区间, 优化后的时间复杂度为. 动态规划状态定义: f[l]...

动态规划前缀和

2020-05-14

0 503