DP：状态机模型

reso1mi 收录于算法

2022-01-01 约 3579 字预计阅读 8 分钟

1049. 大盗阿福

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

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

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

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

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

输入格式

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

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

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

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

输出格式

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

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

数据范围

$1≤T≤50$
$1≤N≤10^5$

输入样例：

输出样例：

8
24

样例解释

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

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

解法一

这题 lc 上写过，还是比较简单，不过不是状态机的做法， $f_i$ 代表的是偷前 $i$ 个房子的最大收益，然后直接线性 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

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

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

定义状态为 $dp_{i,j}$ ，偷前 $i$ 个房子，且第 $i$ 个房子状态为 $j$ （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

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1≤N≤10^5$
$1≤k≤100$

输入样例 1：

3 2
2 4 1

输出样例 1：

输入样例 2：

6 2
3 2 6 5 0 3

输出样例 2：

样例解释

样例 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 上的题，但是这里重写的时候没写出来。重新捋了思路，比之前的要更加清晰，希望下次可以直接写出来。

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

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

定义状态为： $dp[i][j][k]$ ，代表购买前 $i$ 天的股票，进行了恰好 $j$ 次交易，最终状态为 $k$ （0 空仓，1 持仓）

入口： $dp[i][0][0]$ ，不交易就不会持有股票，收益为 0, 其他状态收益为 $\inf$ ，避免非法转移
状态转移：
- $dp[i][j][0] = \max(dp[i-1][j][1] + price, dp[i-1][j][0])$
- $dp[i][j][1] = \max(dp[i-1][j-1][0] - price, dp[i-1][j][1])$
出口： $\max_{j=0}^{k}(dp[N][j][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$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格，再给定一个非负整数 $f$ ，表示交易股票的手续费用。

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1≤N≤10^5$
$1≤f≤10000$

输入样例：

6 2
1 3 2 8 4 9

输出样例：

样例解释

在第 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

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

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

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

输入格式

第一行包含整数 $N$ ，表示数组长度。

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

输出格式

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

数据范围

$1≤N≤10^5$

输入样例：

5
1 2 3 0 2

输出样例：

样例解释

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

解法一

个人觉得这题直接线性 DP 就好了，状态机的反而不容易理解。设置 $dp[i][j]$ 为考虑前 $i$ 天的股票，第 $i$ 天的状态为 $j$ (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. 设计密码

你现在需要设计一个密码 $S$ ， $S$ 需要满足：

$S$ 的长度是 $N$ ；
$S$ 只包含小写英文字母；
$S$ 不包含子串 $T$ ；

例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。

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

由于答案会非常大，请输出答案模 $10^9+7$ 的余数。

输入格式

第一行输入整数 $N$ ，表示密码的长度。

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

输出格式

输出一个正整数，表示总方案数模 $10^9+7$ 后的结果。

数据范围

$1≤N≤50$
$1≤|T|≤N$ ， $|T|$ 是 $T$ 的长度

输入样例 1：

2
a

输出样例 1：

输入样例 2：

4
cbc

输出样例 2：

解法一

这里实际上是一个比较复杂的状态机，还结合了 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：状态机模型

1049. 大盗阿福

解法一

1057. 股票买卖 IV

解法一

1059. 股票买卖 VI

解法一

1058. 股票买卖 V

解法一

1052. 设计密码

解法一