背包问题
for i := 1; i <= N; i++ {
for j := V; j >= v[i]; j-- {
dp[j] = max(dp[j], dp[j - v[i]] + w[i] )
}
}
for i := 1; i <= N; i++ {
for j := v[i]; j <= V; j++ {
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
}
}
for i := 1; i <= N; i++ {
for j := 0; j <= V; j++ {
for k := 0; k <= s[i] && k * v[i] <= j; k++ {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i])
}
}
}
for i := 1; i <= N; i++ {
for j := V; j >= v[i]; j-- {
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
}
}
关键是如何给输入数据进行二进制分组
fmt.Scanln(&N, &V)
for i := 1; i <= N; i++ {
fmt.Scanln(&tmpV, &tmpW, &tmpS)
k := 1
for k <= tmpS {
cur += 1
v = append(v, k * tmpV)
w = append(w, k * tmpW)
tmpS -= k
k *= 2
}
if tmpS > 0 {
cur += 1
v = append(v, tmpS * tmpV)
w = append(w, tmpS * tmpW)
}
}
N = cur
for i := 1; i <= N; i++ {
for j := V; j >= 0; j-- {
for k := 1; k <= s[i]; k++ {
if v[i][k] <= j { dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]) }
}
}
}
线性DP
for i := range dp {
dp[i] = make([]int, n + 1)
for j := range dp[i] { dp[i][j] = -1 << 31 - 1 }
}
dp[1][1] = tri[1][1]
for i := 2; i <= n; i++ {
for j := 1; j <= i; j++ {
dp[i][j] = max(dp[i - 1][j - 1] + tri[i][j], dp[i - 1][j] + tri[i][j])
}
}
for i := 1; i <= n; i++ { ans = max(ans, dp[n][i]) }
for i := 1; i <= N; i++ { dp[i] = 1 }
for i := 1; i <= N; i++ {
for j := 1; j < i; j++ {
if arr[i] > arr[j] { dp[i] = max(dp[i], dp[j] + 1) }
}
}
for i := range dp { ans = max(ans, dp[i]) }
for i := 1; i <= N; i++ {
left, right := 0, len
for left < right {
mid := (left + right + 1) >> 1
if dp[mid] < arr[i] {
left = mid
} else {
right = mid - 1
}
}
len = max(len, right + 1)
dp[right + 1] = arr[i]
}
return len
for i := 1; i <= N; i++ {
for j := 1; j <= M; j++ {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
if A[i] == B[j] { dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1) }
}
}
for i := 0; i <= n; i++ { dp[i][0] = i }
for j := 0; j <= m; j++ { dp[0][j] = j }
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
if A[i] == B[j] {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
} else {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
}
}
}
//复用902的核心代码
func dist(N, M int, n, m string) int {
var (
min = func(i, j int) int { if i < j { return i }; return j }
dp = make([][]int, N + 1)
)
for i := range dp { dp[i] = make([]int, M + 1) }
for i := 0; i <= N; i++ { dp[i][0] = i }
for j := 0; j <= M; j++ { dp[0][j] = j }
for i := 1; i <= N; i++ {
for j := 1; j <= M; j++ {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
if n[i] == m[j] {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
} else { dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1) }
}
}
return dp[N][M]
}
区间DP
for len := 2; len <= N; len++ {
for i := 1; i + len - 1 <= N; i++ {
l, r := i, i + len - 1
dp[l][r] = 1 << 31 - 1
for k := l; k < r; k++ { dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + n[r] - n[l - 1]) }
}
}
return dp[1][N]
计数类DP
dp[0] = 1
for i := 1; i <= N; i++ {
for j := i; j <= N; j++ { dp[j] = (dp[j] + dp[j - i]) % mod }
}
数位统计DP
func get(num []int, l, r int) (res int) {
for i := l; i >= r; i-- { res = res * 10 + num[i] }
return
}
func power10(x int) (res int) {
res = 1
for ; x > 0; x-- { res *= 10 }
return
}
func cal(n, x int) (res int) {
if n == 0 { return 0 }
num := []int{}
for n != 0 {
num = append(num, n % 10)
n /= 10
}
n = len(num)
isZero := 0
if x == 0 { isZero = 1 }
for i := n - 1 - isZero; i >= 0; i-- {
if i < n - 1 {
res += get(num, n - 1, i + 1) * power10(i)
if x == 0 { res -= power10(i) }
}
if num[i] == x {
res += get(num, i - 1, 0) + 1
} else if num[i] > x {
res += power10(i)
}
}
return
}
状态压缩DP
dp[0][0] = 1
for i := 1; i <= m; i++ {
for j := 0; j < 1 << n; j++ {
dp[i][j] = 0
for k := 0; k < 1 << n; k++ {
if j & k == 0 && st[j | k] {
dp[i][j] += dp[i - 1][k]
}
}
}
}
dp空间的初始化也很重要
func initStatus(n int) {
for i := 0; i < 1 << n; i++ {
cnt := 0
st[i] = true
for j := 0; j < n; j++ {
// 遇到1,被占, 且统计的空格数为奇数,无法填充竖着的长方形
if i >> j & 1 > 0 {
if cnt & 1 > 0 {
st[i] = false
break
}
cnt = 0
continue
}
cnt++
}
// 判断剩下的统计数是否奇数
if st[i] && cnt & 1 > 0 { st[i] = false }
}
}
dp[1][0] = 0
for i := 1; i <= 1 << n; i++ {
for j := 0; j < n; j++ {
if (i >> j) & 1 > 0 {
for k := 0; k < n; k++ {
if (i >> k) & 1 > 0 { dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + grep[k][j]) }
}
}
}
}
return dp[(1 << n) - 1][n - 1]
树形DP
func dfs(u int) {
dp[u][1] = happy[u]
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
dfs(j)
dp[u][1] += dp[j][0]
dp[u][0] += max(dp[j][0], dp[j][1])
}
}
记忆化搜索
func dfs(x, y int) int {
if dp[x][y] != -1 { return dp[x][y] }
dp[x][y] = 1
for i := 0; i < 4; i++ {
nx := x + dx[i]
ny := y + dy[i]
if nx >= 1 && nx <= R && ny >= 1 && ny <= C && g[x][y] > g[nx][ny] { dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)}
}
return dp[x][y]
}