2021年1月

【语言学习-日语】 《标准日本语-初级上册》复习笔记

2 条评论 日语 无标签 联环己烷

助词

1.は:提示主语,做助词时读wa。有时用来表强调。

2.を:

与他动词搭配提示宾语 例:私はご飯をたべる。

与自动词搭配提示经过的地点 例:家を出る。


【算法-动态规划】 四边形不等式优化的证明

0 条评论 动态规划 无标签 联环己烷

四边形不等式

对于形如$f(i,j)=\min \{ f(i,k)+f(k+1,j)+w(i,j)\}$形式的DP,若对于$i \leq i' \leq j \leq j'$,有$w(i',j) \leq w(i,j')$(即区间包含单调性)和$w(i,j)+w(i',j') \leq w(i',j)+w(i,j')$(即四边形不等式),则有:

定理1:f也满足四边形不等式,即$f(i,j)+f(i',j') \leq f(i',j)+f(i,j')$

定理2:记g(i,j)为对f(i,j)最优的k,则决策点g(i,j)满足单调性,即$g(i,j) \leq g(i+1,j) \leq g(i,j+1)$

四边形不等式可以简记为“交错小于包含”。


京公网安备 11010802033049号