DP:状态机模型
Resolmi Newbie

1049. 大盗阿福

阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺,每家店中都有一些现金。

阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。

作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。

他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

输入格式

输入的第一行是一个整数 T,表示一共有 T 组数据。

接下来的每组数据,第一行是一个整数 N ,表示一共有 N 家店铺。

第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过 1000。

输出格式

对于每组数据,输出一行。

该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

输入样例:

2
3
1 8 2
4
10 7 6 14

输出样例:

8
24

样例解释

对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8。

对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10+14=24。

解法一

这题 lc 上写过,还是比较简单,不过不是状态机的做法,代表的是偷前个房子的最大收益,然后直接线性 dp

T = int(input())

while T > 0:
n = int(input())
nums = list(map(int, input().split()))
f = [0] * (n+1)
for i in range(1, n+1):
f[i] = max(f[i-1], (f[i-2] + nums[i-1]) if i-2 >= 0 else nums[i-1])
print(f[i])
T -= 1

用状态机来理解,每个房子有两种状态,「偷」或则「不偷」

  • 偷,那么就得保证前一个房子「不偷」
  • 不偷,那么就可以从前一个房子「偷或者不偷」状态转移过来,不影响当前状态

定义状态为,偷前个房子,且第个房子状态为(0 不偷,1 偷)

T = int(input())

while T > 0:
n = int(input())
nums = list(map(int, input().split()))
f = [[0 for _ in range(2)] for _ in range(n+1)]
for i in range(1, n+1):
f[i][0] = max(f[i-1][1], f[i-1][0])
f[i][1] = f[i-1][0] + nums[i-1]
print(max(f[n][1], f[n][0]))
T -= 1

比较 trick 的空间优化写法

T = int(input())

while T > 0:
n = int(input())
nums = list(map(int, input().split()))
f = [0] * 2
for i in range(1, n+1):
f[0], f[1] = max(f[1], f[0]), f[0] + nums[i-1]
print(max(f[1], f[0]))
T -= 1

1057. 股票买卖 IV

给定一个长度为 的数组,数组中的第 个数字表示一个给定股票在第 天的价格。

设计一个算法来计算你所能获取的最大利润,你最多可以完成 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。

输入格式

第一行包含整数 ,表示数组的长度以及你可以完成的最大交易数量。

第二行包含 个不超过 的正整数,表示完整的数组。

输出格式

输出一个整数,表示最大利润。

数据范围

输入样例 1:

3 2
2 4 1

输出样例 1:

2

输入样例 2:

6 2
3 2 6 5 0 3

输出样例 2:

7

样例解释

样例 1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

样例 2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出,这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

解法一

也是 lc 上的题,但是这里重写的时候没写出来。重新捋了思路,比之前的要更加清晰,希望下次可以直接写出来。

从状态机的角度考虑,有两个状态:「持仓」和「空仓」。围绕这两个状态进行转换。

  1. 从「持仓」到「空仓」的转换,说明卖掉了昨天手中持有的股票,并且完成了一次完整交易。或者今天按兵不动,维持前一天的状态
  2. 从「空仓」到「持仓」的转换,说明今天又购入了新的股票,开始了一轮新的交易。或者今天按兵不动,维持前一天的状态

定义状态为:,代表购买前天的股票,进行了恰好次交易,最终状态为(0 空仓,1 持仓)

  • 入口:,不交易就不会持有股票,收益为 0, 其他状态收益为,避免非法转移
  • 状态转移:
  • 出口:

代码实现如下:

import java.util.*;
import java.io.*;

class Main {

/*
6 2
3 2 6 5 0 3
*/

static int INF = -0x3f3f3f3f;

public static void main(String ...args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
int[] in = read(br);
int N = in[0], K = in[1];
int[] price = read(br);
if (K > N/2) {
out.println(maxProfit(price));
out.flush();
return;
}
// dp[N][K][2] 的写法
// 前 i 天,交易次数恰好为 j,第 i 天状态为 k(0 不持有,1 持有)
int[][][] dp = new int[N+1][K+1][2];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
Arrays.fill(dp[i][j], INF);
}
// 不交易就不会持有,收益永远为 0
dp[i][0][0] = 0;
}
int res = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
dp[i][j][0] = Math.max(dp[i-1][j][1] + price[i-1], dp[i-1][j][0]);
// 根据题目限制,当想要再次买入的时候,应该从上一次交易完成后的状态转移过来
// 而买入卖出为一次完整交易,所以上一次交易完成的状态应该为不持有股票
dp[i][j][1] = Math.max(dp[i-1][j-1][0] - price[i-1], dp[i-1][j][1]);
res = Math.max(dp[i][j][0], res);
}
}
out.println(res);
out.flush();
}

public static int maxProfit(int[] price) {
int N = price.length;
int[][] dp = new int[N+1][2];
for (int i = 0; i <= N; i++) {
Arrays.fill(dp[i], INF);
}
dp[0][0] = 0;
int res = 0;
for (int i = 1; i <= N; i++) {
dp[i][0] = Math.max(dp[i-1][1] + price[i-1], dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][0] - price[i-1], dp[i-1][1]);
res = Math.max(dp[i][0], res);
}
return res;
}

public static int[] read(BufferedReader br) throws Exception{
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

这里就不写降维的了,降维会隐藏一些信息。最好是先写出原始的,如果 MLE 了,再考虑降维。直接写降维的可能会不知道怎么对的,也不知道怎么错的(太菜了)。

1059. 股票买卖 VI

给定一个长度为 的数组,数组中的第 个数字表示一个给定股票在第 天的价格,再给定一个非负整数 ,表示交易股票的手续费用。

设计一个算法来计算你所能获取的最大利润。

你可以无限次地完成交易,但是你每次交易都需要支付手续费。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入格式

第一行包含两个整数 N 和 f,分别表示数组的长度以及每笔交易的手续费用。

第二行包含 N 个不超过 10000 的正整数,表示完整的数组。

输出格式

输出一个整数,表示最大利润。

数据范围

输入样例:

6 2
1 3 2 8 4 9

输出样例:

8

样例解释

在第 1 天(股票价格 = 1)的时候买入,在第 4 天(股票价格 = 8)的时候卖出,这笔交易所能获得利润 = 8-1-2 = 5 。随后,在第 5 天(股票价格 = 4)的时候买入,在第 6 天 (股票价格 = 9)的时候卖出,这笔交易所能获得利润 = 9-4-2 = 3 。共得利润 5+3 = 8。

解法一

package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

var reader = bufio.NewReader(os.Stdin)

func main() {
INF := int(-0x3f3f3f3f)
// f, _ := os.Open("./input.txt")
// reader := bufio.NewReader(f)
reader := bufio.NewReader(os.Stdin)
in := ReadArray(reader)
N, F := in[0], in[1]
price := ReadArray(reader)

dp := make([][]int, N+1)
for i := 0; i <= N; i++ {
dp[i] = make([]int, 2)
dp[i][0] = INF
dp[i][1] = INF
}

dp[0][0] = 0
res := 0
for i := 1; i <= N; i++ {
dp[i][0] = Max(dp[i-1][1]+price[i-1]-F, dp[i-1][0])
dp[i][1] = Max(dp[i-1][0]-price[i-1], dp[i-1][1])
res = Max(res, dp[i][0])
}
fmt.Println(res)
}

func Max(a, b int) int {
if a > b {
return a
}
return b
}

func ReadLine(reader *bufio.Reader) string {
line, _ := reader.ReadString('\n')
return strings.TrimRight(line, "\n")
}

func ReadInt(reader *bufio.Reader) int {
num, _ := strconv.Atoi(ReadLine(reader))
return num
}

func ReadArray(reader *bufio.Reader) []int {
line := ReadLine(reader)
strs := strings.Split(line, " ")
nums := make([]int, len(strs))
for i, s := range strs {
nums[i], _ = strconv.Atoi(s)
}
return nums
}

1058. 股票买卖 V

给定一个长度为 的数组,数组中的第 个数字表示一个给定股票在第 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

输入格式

第一行包含整数 ,表示数组长度。

第二行包含 个不超过 10000 的正整数,表示完整的数组。

输出格式

输出一个整数,表示最大利润。

数据范围

输入样例:

5
1 2 3 0 2

输出样例:

3

样例解释

对应的交易状态为:[买入,卖出,冷冻期,买入,卖出],第一笔交易可得利润 2-1 = 1,第二笔交易可得利润 2-0 = 2,共得利润 1+2 = 3。

解法一

个人觉得这题直接线性 DP 就好了,状态机的反而不容易理解。设置为考虑前 天的股票,第天的状态为(0 为空仓,1 为持仓)

package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

var reader = bufio.NewReader(os.Stdin)

func main() {
n := ReadInt(reader)
price := ReadArray(reader)
dp := make([][2]int, n+1)
dp[0][1] = -price[0]
var res = 0
for i := 1; i <= n; i++ {
dp[i][0] = Max(dp[i-1][1]+price[i-1], dp[i-1][0])
if i-2 >= 0 {
dp[i][1] = Max(dp[i-2][0]-price[i-1], dp[i-1][1])
} else {
dp[i][1] = Max(-price[i-1], dp[i-1][1])
}
res = Max(res, dp[i][0])
}
fmt.Println(res)
}

func Max(a, b int) int {
if a > b {
return a
}
return b
}

func ReadLine(reader *bufio.Reader) string {
line, _ := reader.ReadString('\n')
return strings.TrimRight(line, "\n")
}

func ReadInt(reader *bufio.Reader) int {
num, _ := strconv.Atoi(ReadLine(reader))
return num
}

func ReadArray(reader *bufio.Reader) []int {
line := ReadLine(reader)
strs := strings.Split(line, " ")
nums := make([]int, len(strs))
for i, s := range strs {
nums[i], _ = strconv.Atoi(s)
}
return nums
}

1052. 设计密码

你现在需要设计一个密码 需要满足:

  • 的长度是
  • 只包含小写英文字母;
  • 不包含子串

例如:abc 和 abcde 是 abcde 的子串,abd 不是 abcde 的子串。

请问共有多少种不同的密码满足要求?

由于答案会非常大,请输出答案模 的余数。

输入格式

第一行输入整数 ,表示密码的长度。

第二行输入字符串 中只包含小写字母。

输出格式

输出一个正整数,表示总方案数模 后的结果。

数据范围

  • 的长度

输入样例 1:

2
a

输出样例 1:

625

输入样例 2:

4
cbc

输出样例 2:

456924

解法一

这里实际上是一个比较复杂的状态机,还结合了kmp,属实是有点难了,我也看了好久。这里建议先熟悉下kmp,这里我也更新了我之前的kmp的写法。

package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

var MOD = int(1e9 + 7)

func main() {
f, _ := os.Open("../input.txt")
reader := bufio.NewReader(f)
// reader := bufio.NewReader(os.Stdin)
n := ReadInt(reader)
t := ReadLine(reader)
m := len(t)
dp := make(map[int]map[int]int)
for i := 0; i <= n; i++ {
dp[i] = make(map[int]int)
}
// 构建next数组
next := make([]int, m)
next[0] = -1
for i, j := -1, 1; j < m; j++ {
for i > -1 && t[i+1] != t[j] {
i = next[i]
}
if t[i+1] == t[j] {
i++
}
next[j] = i
}
// 长度为0,必然不包含子串
dp[0][-1] = 1
for i := 0; i < n; i++ { // 密码长度
for c := 'a'; c <= 'z'; c++ { // 密码第i-1位字符
for j := -1; j < m-1; j++ { // 密码第i-1位在子串的状态
u := j
for u > -1 && byte(c) != t[u+1] {
u = next[u]
}
if byte(c) == t[u+1] {
u++
}
// j -> u 的状态变化,如果u < m-1 也就说明下一个字符为c状态为u时仍然不匹配
// 故 dp[i+1][u] += dp[i][j]
if u < m-1 {
dp[i+1][u] = (dp[i+1][u] + dp[i][j]) % MOD
}
}
}
}
var res = 0
for i := -1; i < m-1; i++ {
res = (res + dp[n][i]) % MOD
}
fmt.Println(res)
}

func ReadLine(reader *bufio.Reader) string {
line, _ := reader.ReadString('\n')
return strings.TrimRight(line, "\n")
}

func ReadInt(reader *bufio.Reader) int {
num, _ := strconv.Atoi(ReadLine(reader))
return num
}
  • 本文标题:DP:状态机模型
  • 本文作者:Resolmi
  • 创建时间:2022-01-01 00:00:00
  • 本文链接:https://imlgw.top/2022/01/01/2fc471b9/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论