days

在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。

在接下来的一年里你要旅行的日子将以一个名为

days

令dp[i]表示第i天所需的最小花费用st数组记录第i天是否需要旅游状态转移如下

if\

dp[i]min(dp[max(0,i-1/7/30)]val[1/7/30]

vis[i]

dp[i]min(dp[max(0,i−1/7/30)]val[1/7/30]这里若i不足1/7/30天可以从第0天直接开始买

else

是数组中连续的一个元素序列。

arr[left...right]

表示子数组包含

本质是子数组最大和构建一个新数组值为nums1和nums2的差此时只需要找最大子数组t1和和最小子数组和t2令nums1的和为sum1nums2的和为sum2则答案就是max(sum1-t2,sum2t1)

class

的珠宝架其中frame[i][j]为该位置珠宝的价值。

拿取珠宝的规则为

frame

dp[i][j]max(dp[i][j-1],dp[i-1][j])v

dp[i][j]max(dp[i][j−1],dp[i−1][j])v

主要讲一下空间压缩对于dp[i],只用到了dp[i-1]的数据计算完后dp[i-1]因此可以将dp[i]的数据存到dp[i-1]的地方再想一下其实两个数组就够了只需要下标对2取模dp[i]的值存到dp[i%2]的位置使用dp[i-1]的值就是使用dp[(i-1)%2]的值

class