Contest1874 – noip基础知识五：动态规划(背包、树dp、记忆化、递推、区间、序列dp、dp优化)

传送门

T1  dp[n][m]=dp[n-1][m-1]+dp[n-m][m]

T2  ans=cat(n)*(n!)²  卡特兰数

T3  dp[i][j]=sigma(dp[i-1][j-a[i]])

T4  二进制拆分，01背包

T5  二维费用背包问题

T6  dp[i][j]=max(dp[i-1][k]*num[k+1][i]),k<i

T7  dp[i][j]=max(dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])，i<=k<j。

T8 满背包问题

T9  dp[i][j]=min(dp[i][k]+dp[k+1][j]+s[j]-s[i-1]),i<=k<j,s数组是前缀和

T10 dp[u][0]=sigma(max(dp[son][0],dp[son][1])),dp[u][1]=sigma(dp[son][0])

T11  dp[i]=max(dp[j])+1,j<i&&a[j]<a[i]