牛客844784119号

经典题型

图(1) 总结(9)

/ 注册

全部文章 / 经典题型（共4篇）

最长公共子序列（LCS）

1.最长公共子序列的定义：我们称序列Z=<z1,z2,...,zk>，Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>X=<x1,x2,...,xm>的子序列当且仅当存在严格上升的序列<i1,i2,...,ik>&...

动态规划

2020-02-07

1 981

最长不下降子序列（LIS）

一：最长不下降子序列状态转移方程： f[i]=max(f[(0--i-1)]+1,f[i]) //f[i]指以i结尾的的最长不下降子序列的最长长度二:具体思路: 正确思路...

动态规划

2020-01-28

1 775

01背包详解

一.01背包状态转移方程解析：原方程 f(i,j)=max(f(i-1,j),f(i-1,j-w[i])+c[i]))1.f(i,j)表示前i件物品放到容积为j的背包中的最大价值，w[i]表示第i件物品的重量，c[i]表示第i件物品的价值 2.一件物...

动态规划

2020-01-26

1 527

数字三角形详解

数字三角形状态转移方程(由底层向顶层)： a[i][j]=max(a[i+1][j+1],a[i+1][j])+a[i][j]（数组a为输入存储数组，n为层数，同时也是列数，a[i][j]表示该点到底层的最大权值之和（即最长路径））...

动态规划

2020-01-17

2 440