DP：状态机模型
Resolmi Newbie
 2022-01-01 00:00:00      3.3k 字  14 分钟  

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 许可协议。转载请注明出处！
 评论