一、考察频率以及难度

考察频率：⭐⭐⭐⭐⭐

笔试题难度：⭐⭐⭐

算法难度：⭐⭐⭐

一般笔试出现的难度是中等题。

二、学习技巧

需要积累一些常见的dp模型，比如最简单的斐波那契类型的，F[n] = F[n-1] + F[n-2]。如果没有做过类似的dp模型，还是比较难在笔试的时候想出来的。

三、应用场景

经典的应用场景：斐波那契、最长上升子序列、最大子数组和等。

四、算法讲解

线性DP的基本思想是通过构建一个状态数组或状态表，在每个状态处存储一个问题的子问题的最优解，然后利用这些子问题的最优解来构建更大的问题的最优解。最终，通过从小到大逐步推进，得到原问题的最优解。

1. 斐波那契

斐波那契数列是最简单的线性DP问题之一。状态转移方程为：

f[i] = f[i-1] + f[j-1]

2. 最长上升子序列

给定一个数组，找到其最长的严格递增子序列的长度。状态转移方程为：

f[i] = max(f[j]) + 1 , 0<=j<i 且 nums[j]<nums[i]

3. 最大子数组和

给定一个数组，找到其连续子数组的最大和。状态转移方程为：

f[i] = max(nums[i], f[i-1]+nums[i])

4. 最长公共子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

状态定义：f[i][j]表示包含nums1的第 i 个数字和包含nums2的第j个数字的最长重复子数组的长度。

转移为：

5. 最长公共子序列

找到两个序列（如字符串或数组）中最长的公共子序列，使得这个子序列在两个序列中出现的顺序一致，但不要求连续。

状态定义： f[i][j]表示序列X的前i个字符和序列Y的前j个字符的最长公共子序列的长度。

转移为：

五、例题与解析

习题1 斐波那契数列

https://oj.niumacode.com/problem/P1106

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：

2

输出：

1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：

3

输出：

2

解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：

4

输出：

3

解释：F(4) = F(3) + F(2) = 2 + 1 = 3

 

提示：

0 <= n <= 30

题目解析

此题是动态规划最简单的题目之一。

1. 状态转移方程式：题目已经明确告诉我们，F(n) = F(n - 1) + F(n - 2)

2. 容器规模：数组表示的范围是[0, n]，因此数组大小定义为n+1

3. base case：对于任意的i，都只依赖于i - 1和i - 2，因此我们只需要将数组下标为0和下标为1预先填好，后面所有的值都按照式子即可填满表中所有的值。

4. 填表顺序：从下标为2开始往后填表即可

代码展示

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        
        if (n == 0) {
            System.out.println(0);
        } else if (n == 1) {
            System.out.println(1);
        } else {
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            System.out.println(dp[n]);
        }
        
        scanner.close();
    }
}

Python

n = int(input())
if n==0:
    print(0)
elif n==1:
    print(1)
else:
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[-1])

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    if (n == 0) {
        cout << 0 << endl;
    } else if (n == 1) {
        cout << 1 << endl;
    } else {
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        cout << dp[n] << endl;
    }
    
    return 0;
}

习题2 最长递增子序列

https://oj.niumacode.com/problem/P1107

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：

8
10 9 2 5 3 7 101 18

输出：

4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]

6
0 1 0 3 2 3

输出：

4

示例 3：

输入：nums = [7,7,7,7,7,7,7]

7
7 7 7 7 7 7 7

输出：

1

 

提示：

1 <= nums.length <= 2500

-10^4 <= nums[i] <= 10^4

题目解析

1. 状态转移方程式：dp[i]表示包含第i位的最长递增子序列的长度。因此dp[i] = max(dp[i], dp[j] + 1)，其中j∈[0, i - 1]

2. 容器规模：i∈[0, length - 1]

3. base case：dp数组全部赋值为1（最少肯定是1）

4. 顺序：从1开始往后填表即可

代码展示

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        
        System.out.println(ans);
        
        scanner.close();
    }
}

Python

n = int(input())
nums = [int(c) for c in input().split()]
dp = [1] * len(nums)
ans = 1
for i in range(1, len(nums)):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)
        ans = max(ans, dp[i])
print(ans)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<int> dp(n, 1);
    int ans = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;

    return 0;
}

习题3 最长重复子数组

https://oj.niumacode.com/problem/P1108

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：

5 5
1 2 3 2 1
3 2 1 4 7

输出：

3

解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：

5 5
0 0 0 0 0
0 0 0 0 0

输出：

5

提示：

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 100

题目解析

LCS属于经典的动态规划问题，同时也是面试场考题，同学们一定要熟悉！

1. 状态转移方程式：dp[i][j]表示包含nums1的第 i 个数字和包含nums2的第j个数字的最长重复子数组的长度。if nums1[i] == nums[j]: dp[i][j] = dp[i - 1][j - 1] + 1; else: dp[i][j] = 0

2. 容器规模：i的范围是[0, len1] j的范围是[0, len2]

3. base case：由于依赖关系如下因此basecase应该是第一行和第一列（红色部分）因此，basecase是dp[0][j]和dp[i][0]，二者均为0。

4. 填表顺序：从[1, 1]开始从左往右，从上到下填表即可。

代码展示

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] nums1 = new int[n];
        int[] nums2 = new int[m];
        
        for (int i = 0; i < n; i++) {
            nums1[i] = scanner.nextInt();
        }
        
        for (int i = 0; i < m; i++) {
            nums2[i] = scanner.nextInt();
        }
        
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        
        System.out.println(ans);
        
        scanner.close();
    }
}

Python

class Solution:
    def findLength(self, nums1, nums2):
        len1, len2 = len(nums1), len(nums2)
        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        ans = 0
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
        return ans

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> nums1(n);
    vector<int> nums2(m);

    for (int i = 0; i < n; i++) {
        cin >> nums1[i];
    }

    for (int i = 0; i < m; i++) {
        cin >> nums2[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

习题4 最长公共子序列

https://oj.niumacode.com/problem/P1109

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：

5 3
abcde
ace

输出：3

3

解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：

3 3
abc
abc

输出：

3

解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：

3 3
abc
def

输出：

0

解释：两个字符串没有公共子序列，返回 0 。

 

提示：

1 <= text1.length, text2.length <= 1000

text1 和 text2 仅由小写英文字符组成。

题目解析

同样属于LCS问题中的一类，属于面试常考题，一定要熟悉。

1. 状态转移方程式：dp[i][j]表示text1的前 i 个字符和text2的前 j 个字符的最长公共子序列的长度。如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

2. 容器规模：i属于[0, text1.length] j属于[0, text2.length]

3. base case：dp[0][j]和dp[i][0] 二者均为0。

4. 填表顺序：从[1, 1]开始从左往右，从上到下填表即可。

代码展示

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int len1 = scanner.nextInt();
        int len2 = scanner.nextInt();
        scanner.nextLine();  // consume the newline character
        String text1 = scanner.nextLine();
        String text2 = scanner.nextLine();
        
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        System.out.println(dp[len1][len2]);
        
        scanner.close();
    }
}

Python

len1,len2 = map(int, input().split())
text1 = input()
text2 = input()
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if text1[i - 1] == text2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[len1][len2])

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int len1, len2;
    cin >> len1 >> len2;
    string text1, text2;
    cin>> text1;
    cin >> text2;

    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[len1][len2] << endl;

    return 0;
}

习题5 编辑距离

https://oj.niumacode.com/problem/P1110

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符

• 删除一个字符

• 替换一个字符

示例 1：

输入：

5 3
horse
ros

输出：

3

解释：

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

示例 2：

输入：

9 9
intention
execution

输出：

5

解释：

intention -> inention (删除 't')

inention -> enention (将 'i' 替换为 'e')

enention -> exention (将 'n' 替换为 'x')

exention -> exection (将 'n' 替换为 'c')

exection -> execution (插入 'u')

 

提示：

0 <= word1.length, word2.length <= 500

word1 和 word2 由小写英文字母组成

题目解析

1. 状态转移方程式：dp[i][j]考虑word1的前 i 个字符和word2的前 j 个字符转为相同的最小步数。如果word1[i]==word2[j]那么说明这一位是不需要删除的，此时dp[i][j]=dp[i-1][j-1]。否则，要么删除word1的第i个字符，此时dp[i][j] = dp[i - 1][j] + 1；要么插入一个字符在word1后面，与word2匹配，此时dp[i][j] = dp[i][j - 1] + 1; 要么将word1的第i个字符替换成与word2的第j个字符一致，此时dp[i][j] = dp[i - 1][j - 1] + 1，在三种操作中选取最小的即可。

2. 容器规模：i属于[0,len1]，j属于[0,len2]

3. base case：依赖关系与“最长公共子序列”一致，因此basecase是dp[0][j]和dp[i][0]，其中dp[0][j] = j, dp[i][0] = i

4. 填表顺序：从[1, 1]开始从左往右，从上到下填表即可。

代码展示

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int len1 = scanner.nextInt();
        int len2 = scanner.nextInt();
        scanner.nextLine();  // consume the newline character
        String word1 = scanner.nextLine();
        String word2 = scanner.nextLine();
        
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i;
        }
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        
        System.out.println(dp[len1][len2]);
        
        scanner.close();
    }
}

Python

len1, len2 = map(int, input().split())
word1 = input()
word2 = input()
dp = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]
for j in range(1, len2 + 1):
    dp[0][j] = j
for i in range(1, len1 + 1):
    dp[i][0] = i
for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if word1[i - 1] == word2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

print(dp[len1][len2])

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int len1, len2;
    cin >> len1 >> len2;
    string word1, word2;
    cin >> word1;
    cin >> word2;
    
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    
    for (int j = 1; j <= len2; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= len1; i++) {
        dp[i][0] = i;
    }
    
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            }
        }
    }
    
    cout << dp[len1][len2] << endl;
    
    return 0;
}

习题6 魔法师 【百度】

https://oj.niumacode.com/problem/P1143

魔法师小树有n个魔法元素，他把它们排成一行，从左到右第i个魔法元素的能量值是一个非零整数ai。小树每次施展魔法的方式是挑选一段连续非空的魔法元素,将它们的能量值乘起来，得到值就是这次魔法的总能量。如果总能量大于零即为白风法,否则为黑魔法。

现在小树想知道施展—个白魔法或黑魔法的方案数分别有多少。两个方案不同是指挑选的连续区间不同。

输入描述

第一行有一个整数n(1<= n <= 2 * 10^5),表示魔法元素的个数。

第二行有n个整数a1,a2,....,an (-10^9 <= ai <= 10^9; ai != 0)代表魔法元素的能量值。

输出描述

输出两个整数，分别表示施展一个黑魔法和施展一个白魔法的方案数

测试样例

输入

5
5 -3 3 -1 1

输出

8 7

代码展示

动态规划。

一个非常基础的线性dp的问题。

我们定义 ：

1. dp1[i]表示以第i个元素结尾，乘积为正的子串数量

2. dp2[i]表示以第i个元素结尾，乘积为负的子串数量

初始情况下：

• 如果 a[0] > 0，那么 dp1[0] = 1，否则为 0。

• 如果 a[0] < 0，那么 dp2[0] = 1，否则为 0。

然后我们遍历数组，对于每一个元素 a[i]：

• 如果 a[i] > 0，那么 dp1[i] 等于 dp1[i-1] + 1，dp2[i] 等于 dp2[i-1]。

• 如果 a[i] < 0，那么 dp1[i] 等于 dp2[i-1]，dp2[i] 等于 dp1[i-1] + 1。

最终，我们将 dp1 和 dp2 所有元素的和分别赋值给 w 和 b。

C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a[n];
    for (int i = 0; i < n; i++) {
    cin >> a[i];
    }
    long long dp1[n]; //以第i个元素结尾，乘积为正的子串数量
    long long dp2[n]; //以第i个元素结尾，乘积为负的子串数量
    
    dp1[0] = a[0] > 0 ? 1 : 0;
    dp2[0] = a[0] < 0 ? 1 : 0;
    
    long long w = dp1[0], b = dp2[0];
    
    for (int i = 1 ; i < n ; i++) {
        if (a[i] > 0) {
            dp1[i] = 1 + dp1[i - 1];
            dp2[i] = dp2[i - 1];
        }
        else {
            dp1[i] = dp2[i - 1];
            dp2[i] = dp1[i - 1] + 1;
        }
        w += dp1[i];
        b += dp2[i];
    }
    
    cout << b << " " << w << endl;
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        long[] dp1 = new int[n]; // 以第i个元素结尾，乘积为正的子串数量
        long[] dp2 = new int[n]; // 以第i个元素结尾，乘积为负的子串数量

        dp1[0] = a[0] > 0 ? 1 : 0;
        dp2[0] = a[0] < 0 ? 1 : 0;

        long w = dp1[0];
        long b = dp2[0];

        for (int i = 1; i < n; i++) {
            if (a[i] > 0) {
                dp1[i] = 1 + dp1[i - 1];
                dp2[i] = dp2[i - 1];
            } else {
                dp1[i] = dp2[i - 1];
                dp2[i] = dp1[i - 1] + 1;
            }
            w += dp1[i];
            b += dp2[i];
        }

        System.out.println(b + " " + w);
    }
}

Python

def main():
    n = int(input())
    a = list(map(int, input().split()))

    dp1 = [0] * n  # 以第i个元素结尾，乘积为正的子串数量
    dp2 = [0] * n  # 以第i个元素结尾，乘积为负的子串数量

    dp1[0] = 1 if a[0] > 0 else 0
    dp2[0] = 1 if a[0] < 0 else 0

    w = dp1[0]
    b = dp2[0]

    for i in range(1, n):
        if a[i] > 0:
            dp1[i] = 1 + dp1[i - 1]
            dp2[i] = dp2[i - 1]
        else:
            dp1[i] = dp2[i - 1]
            dp2[i] = dp1[i - 1] + 1
        w += dp1[i]
        b += dp2[i]

    print(b, w)

if __name__ == "__main__":
    main()

习题7 最佳规划 【美团】

https://oj.niumacode.com/problem/P1144

题目描述:

小团在一个n *m的网格地图上探索。网格地图上第i行第j列的格子用坐标(i,j)简记。初始时,小团的位置在地图的左上角。即坐标(1,1),地图上的每一个格子上都有一定的金币，特别地,小团位于的初始位置(1,1)上的金币为0。小团在进行探索移动时,可以选择向右移动一格(即从(x,y)到达(x,y+1))或向下移动一格(即从(x,y)到达(x+1,y))。地图上的每个格子都有一个颜色，红色或蓝色。如果小团一次移动前后的两个格子颜色不同，那么他需要支付k个金币才能够完成这一次移动;如果移动前后的两个格子颜色相同,则不需要支付金币。小团可以在任意格子选择结束探索。

现在给你网格地图上每个格子的颜色与金币数量,假设小团初始时的金币数量为0，请你帮助小团计算出最优规划，使他能获得最多的金币,输出能获得的最多金币数量即可。

注意:要求保证小团任意时刻金币数量不小于零。

输入描述

第一行是三个用空格隔开的整数n,m和k，表示网格地图的行数为n，列数为m，在不同颜色的两个格子间移动需要支付k个金币。

接下来n行，每行是一个长度为m的字符串，字符串仅包含字符'R'或'B'。第i行字符串的第j个字符表示地图上第i行第j列的格子颜色。如果字符为'R'，则表示格子颜色为红色，为'B'表示格子颜色为蓝色。

接下来是一个n行m列的非负整数矩阵，第i行第j列的数字表示地图上第i行第j列的格子上的金币数量。保证所有数据中数字大小都是介于[0,10]的整数。

1<=n, m <= 200, 1 <= k <= 5。

输出描述

一个正整数，表示能获得最多金币的数量。

示例1

输入

3 3 2
BBB
RBR
RBR
0 2 3
2 4 1
3 2 2

输出

8

思路与代码

经典的网格类DP思路。

dp[i,j]表示走到[i,j]可以获取的最多金币数，初始值需要填充第一行和第一列的内容。

在这个问题中，k 表示在移动过程中，如果小团从一个颜色的格子移动到另一个不同颜色的格子，需要支付的金币数量。因此，我们在动态规划转移过程中需要考虑以下几点：

1. 如果移动前后的格子颜色相同，则不需要支付金币。

2. 如果移动前后的格子颜色不同，则需要支付 k 个金币。

在转移过程中，我们需要确保小团在任意时刻的金币数量不小于零。这也就是说，如果支付了 k 个金币后，小团的金币数量变成负数，则这种移动是不合法的。

具体含义：

• 当小团从 (i-1, j) 移动到 (i, j) 时：

• 如果颜色相同，则 dp[i][j] = dp[i-1][j] + coins[i][j]。

• 如果颜色不同，则需要支付 k 个金币，因此 dp[i-1][j] 必须大于等于 k 才能进行这种移动。即 dp[i][j] = dp[i-1][j] - k + coins[i][j]。

• 如果支付 k 个金币后 dp[i-1][j] 小于 k，则这种移动不可行。

• 当小团从 (i, j-1) 移动到 (i, j) 时：

• 如果颜色相同，则 dp[i][j] = max(dp[i][j], dp[i][j-1] + coins[i][j])。

• 如果颜色不同，则需要支付 k 个金币，因此 dp[i][j-1] 必须大于等于 k 才能进行这种移动。即 dp[i][j] = max(dp[i][j], dp[i][j-1] - k + coins[i][j])。

• 如果支付 k 个金币后 dp[i][j-1] 小于 k，则这种移动不可行。

CPP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<char>> colors(n, vector<char>(m));
    vector<vector<int>> coins(n, vector<int>(m));

    // Reading colors
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> colors[i][j];
        }
    }

    // Reading coins
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> coins[i][j];
        }
    }

    vector<vector<int>> dp(n, vector<int>(m, 0));

    // Initialize the first column
    for (int i = 1; i < n; i++) {
        if (colors[i][0] == colors[i - 1][0]) {
            dp[i][0] = coins[i][0] + dp[i - 1][0];
        } else {
            if (dp[i - 1][0] < k) break;
            dp[i][0] = dp[i - 1][0] - k + coins[i][0];
        }
    }

    // Initialize the first row
    for (int j = 1; j < m; j++) {
        if (colors[0][j] == colors[0][j - 1]) {
            dp[0][j] = coins[0][j] + dp[0][j - 1];
        } else {
            if (dp[0][j - 1] < k) break;
            dp[0][j] = dp[0][j - 1] - k + coins[0][j];
        }
    }

    // Fill the dp table
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (colors[i][j] == colors[i - 1][j]) {
                dp[i][j] = dp[i - 1][j] + coins[i][j];
            } else {
                if (dp[i - 1][j] >= k) {
                    dp[i][j] = dp[i - 1][j] - k + coins[i][j];
                }
            }
            if (colors[i][j] == colors[i][j - 1]) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + coins[i][j]);
            } else {
                if (dp[i][j - 1] >= k) {
                    dp[i][j] = max(dp[i][j], dp[i][j - 1] - k + coins[i][j]);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
    }

    cout << ans << endl;

    return 0;
}

Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        sc.nextLine(); // consume the remaining newline
        
        char[][] colors = new char[n][m];
        int[][] coins = new int[n][m];

        // Reading colors
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < m; j++) {
                colors[i][j] = line.charAt(j);
            }
        }

        // Reading coins
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                coins[i][j] = sc.nextInt();
            }
        }

        int[][] dp = new int[n][m];

        // Initialize the first column
        for (int i = 1; i < n; i++) {
            if (colors[i][0] == colors[i - 1][0]) {
                dp[i][0] = coins[i][0] + dp[i - 1][0];
            } else {
                if (dp[i - 1][0] < k) break;
                dp[i][0] = dp[i - 1][0] - k + coins[i][0];
            }
        }

        // Initialize the first row
        for (int j = 1; j < m; j++) {
            if (colors[0][j] == colors[0][j - 1]) {
                dp[0][j] = coins[0][j] + dp[0][j - 1];
            } else {
                if (dp[0][j - 1] < k) break;
                dp[0][j] = dp[0][j - 1] - k + coins[0][j];
            }
        }

        // Fill the dp table
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (colors[i][j] == colors[i - 1][j]) {
                    dp[i][j] = dp[i - 1][j] + coins[i][j];
                } else {
                    if (dp[i - 1][j] >= k) {
                        dp[i][j] = dp[i - 1][j] - k + coins[i][j];
                    }
                }
                if (colors[i][j] == colors[i][j - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + coins[i][j]);
                } else {
                    if (dp[i][j - 1] >= k) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] - k + coins[i][j]);
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, Arrays.stream(dp[i]).max().getAsInt());
        }

        System.out.println(ans);

        sc.close();
    }
}

Python

n,m,k = map(int, input().split(" "))
colors = []
for i in range(n):
    colors.append([c for c in input()])
coins = []
for i in range(n):
    coins.append([int(c) for c in input().split(" ")])

dp = [[0 for _ in range(m)] for _ in range(n)]

for i in range(1, n):
    if colors[i][0] == colors[i - 1][0]:
        dp[i][0] = coins[i][0] + dp[i - 1][0]
    else:
        if dp[i - 1][0] < k: break
        dp[i][0] = dp[i-1][0] - k + coins[i][0]

for j in range(1, m):
    if colors[0][j] == colors[0][j-1]:
        dp[0][j] = coins[0][j] + dp[0][j-1]
    else:
        if dp[0][j-1] < k: break
        dp[0][j] = dp[0][j-1] - k + coins[0][k]

for i in range(1, n):
    for j in range(1, m):
        if colors[i][j] == colors[i-1][j]:
            dp[i][j] = dp[i-1][j] + coins[i][j]
        else:
            if dp[i-1][j] >= k:
                dp[i][j] = dp[i-1][j]-k + coins[i][j]
        if colors[i][j] == colors[i][j-1]:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + coins[i][j])
        else:
            if dp[i][j-1] >= k:
                dp[i][j] = max(dp[i][j], dp[i][j-1]-k+coins[i][j])

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))
print(ans)

习题8 水果打包 【美团】

https://oj.niumacode.com/problem/P1149

题目描述：

小美不干外卖配送了，转行开了一家水果店。

一天她接到了一个大单，客户订购了 n 个水果，并且要求打包成多个果篮，一个果篮最多装 m 个水果。

为了包装方便，水果按从 1 到 n 编号，同一个果篮里装的水果编号必须是连续的。果篮的成本与容积成线性关系。为了估计容积，小美简单地用样本中点估计了一下。具体来说，假设一个果篮中装的最大的水果体积是 u，最小的是 v，那么这个果篮的成本就是 k × floor((u+v)/2) + s，其中 k 是果篮中装入水果的个数，s 是一个常数，floor(x) 是下取整函数，比如 floor(3.8)=3, floor(2)=2。

客户并没有规定果篮的数量，但是希望果篮的成本越小越好，毕竟买水果就很贵了。请求出小美打包这 n 个水果所用的最小花费。

输入描述

第一行三个正整数 n, m, s。意义如题面所示。

第二行 n 个正整数 a1, a2, ..., an，表示每个水果的体积。

对于全部数据，1 ≤ n ≤ 10^4,   1 ≤ m ≤ 10^3,   m ≤ n,   1 ≤ ai, s ≤ 10^4。

输出描述

输出一个整数，表示打包这 n 个水果果篮的最小成本。

样例输入

6 4 3 
1 4 5 1 4 1

样例输出

21

提示

样例说明

前三个水果装成一个果篮，后三个水果装成一个果篮。

思路与代码

动态规划。

我们使用动态规划来解决这个问题。设dp[i]表示前i个水果的最小打包成本。

1. 初始条件：

• dp[0] = 0：表示没有水果时的成本为0。

• 其他dp[i]初始化为无穷大，表示尚未计算的状态。

2. 状态转移方程：

• 对于每个水果i，我们考虑将水果从第j个到第i个打包成一个果篮，其中j可以从i-1到i-m。

• 我们需要计算这个果篮的成本，并更新dp[i]。具体来说，dp[i]可以通过以下公式得到：

• dp[i] = min(dp[i], dp[j] + (i - j) * ((max_a + min_a) // 2) + s)

• 其中，max_a和min_a分别是从第j到第i个水果中的最大和最小体积。

3. 计算最小成本：

• 对于每一个i，从1到n，计算dp[i]，最终dp[n]即为最小成本。

CPP

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int minCostToPackFruits(int n, int m, int s, vector<int>& a) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        int max_a = a[i - 1];
        int min_a = a[i - 1];
        for (int j = i - 1; j >= max(i - m, 0); j--) {
            max_a = max(max_a, a[j]);
            min_a = min(min_a, a[j]);
            dp[i] = min(dp[i], dp[j] + (i - j) * ((max_a + min_a) / 2) + s);
        }
    }

    return dp[n];
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << minCostToPackFruits(n, m, s, a) << endl;
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        System.out.println(minCostToPackFruits(n, m, s, a));
    }

    public static int minCostToPackFruits(int n, int m, int s, int[] a) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            int max_a = a[i - 1];
            int min_a = a[i - 1];
            for (int j = i - 1; j >= Math.max(i - m, 0); j--) {
                max_a = Math.max(max_a, a[j]);
                min_a = Math.min(min_a, a[j]);
                dp[i] = Math.min(dp[i], dp[j] + (i - j) * ((max_a + min_a) / 2) + s);
            }
        }

        return dp[n];
    }
}

Python

n, m, s = map(int, input().split())
a = list(map(int, input().split()))

dp = [float('inf')] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    max_a = a[i - 1]
    min_a = a[i - 1]
    for j in range(i - 1, max(i - m - 1, -1), -1):
        max_a = max(max_a, a[j])
        min_a = min(min_a, a[j])
        dp[i] = min(dp[i], dp[j] + (i - j) * ((max_a + min_a) // 2) + s)

print(dp[n])

习题9 互为倍数的子集 【米哈游】

https://oj.niumacode.com/problem/P1151

米小游拿到了一个集合（集合元素互不相等）。她想知道，该集合有多少元素数量大于1的子集，满足子集内的元素两两之间互为倍数关系？结果可能很大，请对10^9+7取模。

输入描述

第一行输入一个正整数n，代表集合大小。

第二行输入n个正整数ai，代表集合元素。

1≤n≤10^5

1≤ai≤10^6

输出描述

一个整数，代表满足题意的子集的数量。

示例1

输入

5
1 2 3 4 5

输出

6

思路与代码

最朴素的思路可以是 dp[i]表示以第i个元素结尾的子集的数量，因此不难写出dp转移方程式：
dp[i] = 1 + sum(dp[j])，其中，nums[i]是nums[j]的倍数。但是这样的操作我们需要枚举j，也就是时间复杂度会去到O(n^2)，对于10w的数据规模是无法通过的。

优化思路如下：我们要枚举的j的特点是必须满足nums[i]是nums[j]的倍数，换句话说，nums[j]是nums[i]的一个因子。因此我们可以更换dp思路，把dp[i]定义为 最大倍数为i的子集的数量。那么我们枚举的时候只需要枚举nums[i]的因子就可以了，枚举因子的复杂度是O(√n)，因此复杂度可以优化为O(n√n)。

CPP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_A = 100010;
const int MOD = 1000000007;

int n;
vector<int> a;
int dp[MAX_A];

vector<int> find_factors(int x) {
    vector<int> factors;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            factors.push_back(i);
            if (i != x / i) {
                factors.push_back(x / i);
            }
        }
    }
    return factors;
}

int main() {
    cin >> n;
    a.resize(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end());
    
    dp[a[0]] = 1;
    
    for (int i = 1; i < n; ++i) {
        vector<int> factors = find_factors(a[i]);
        for (int fac : factors) {
            if (fac != a[i]) {
                dp[a[i]] += dp[fac];
                dp[a[i]] %= MOD;
            }
        }
        dp[a[i]] += 1;
        dp[a[i]] %= MOD;
    }
    
    int sum_dp = 0;
    for (int i = 1; i <= a[n - 1]; ++i) {
        sum_dp += dp[i];
        sum_dp %= MOD;
    }
    
    cout << (sum_dp - n + MOD) % MOD << endl;
    
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int MAX_A = 305;
    static final int MOD = 1000000007;
    static int n;
    static int[] a;
    static int[] dp;

    static List<Integer> findFactors(int x) {
        List<Integer> factors = new ArrayList<>();
        for (int i = 1; i * i <= x; ++i) {
            if (x % i == 0) {
                factors.add(i);
                if (i != x / i) {
                    factors.add(x / i);
                }
            }
        }
        return factors;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new int[n];
        
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }
        
        Arrays.sort(a);
        
        dp = new int[MAX_A];
        dp[a[0]] = 1;
        
        for (int i = 1; i < n; ++i) {
            List<Integer> factors = findFactors(a[i]);
            for (int fac : factors) {
                if (fac != a[i]) {
                    dp[a[i]] += dp[fac];
                    dp[a[i]] %= MOD;
                }
            }
            dp[a[i]] += 1;
            dp[a[i]] %= MOD;
        }
        
        int sum_dp = 0;
        for (int i = 1; i <= a[n - 1]; ++i) {
            sum_dp += dp[i];
            sum_dp %= MOD;
        }
        
        System.out.println((sum_dp - n + MOD) % MOD);
        
        scanner.close();
    }
}

python

n = int(input())
a = [int(c) for c in input().split(" ")]
a.sort()

dp = [0 for _ in range(a[-1] + 1)]
def find_factors(x):
    factors = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            factors.append(i)
            if i != x // i:
                factors.append(x // i)
        i += 1
    return factors

dp[a[0]] = 1
for i in range(1,n):
    factors = find_factors(a[i])
    for fac in factors:
        if fac != a[i]:
            dp[a[i]] += dp[fac]
    dp[a[i]] += 1

print(sum(dp) - n)

习题10 连续子数组最大和 【小红书】

https://oj.niumacode.com/problem/P1163

题目描述：

小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？

输入描述

第一行输入一个正整数t，代表询问次数。

对于每次询问，输入两行：

第一行输入两个正整数n和x。代表数组的大小，以及小红可以修改成的元素。

第二行输入n个正整数a_i，代表小红拿到的数组。

1 ≤ t ≤ 100

1 ≤ n ≤ 20000

-10^9 ≤ x ,a_i ≤ 10^9

每组所有询问的n的和不超过200000。

输出描述

输出t行，每行输出一个整数，代表连续子数组的最大和。

样例输入

3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1

样例输出

15
-2
15

提示

第一组询问，修改第二个数。第二组询问，不进行任何修改。第三组询问，修改第三个数。

思路与代码

首先观察数据范围，发现n是非常大的，所以就应该要先想办法在O(n)或者O(nlogn)时间下计算出每一组查询。

假设修改点为i，不难想到，最后的答案应该是  [0,i-1]中，以i-1结尾的最大和子数组，加上 [i+1,n-1]中，以i+1结尾的最大和子数组，因此我们可以预处理出 正向最大子数组 和 逆向最大子数组，枚举修改点即可。

• 计算从左到右的最大子数组和（dp1）。

• 计算从右到左的最大子数组和（dp2）。

枚举修改点：

• 对于每一个可能的修改点，计算假如修改这个点后的最大子数组和。

• 最后取所有可能情况中的最大值

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<int> dp1(n);
        dp1[0] = a[0];
        int res = INT_MIN;
        for (int i = 1; i < n; i++) {
            dp1[i] = max(dp1[i - 1] + a[i], a[i]);
            res = max(res, dp1[i]);
        }

        vector<int> dp2(n);
        dp2[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            dp2[i] = max(dp2[i + 1] + a[i], a[i]);
        }

        for (int i = 0; i < n; i++) {
            res = max(res, (i > 0 && dp1[i - 1] > 0 ? dp1[i - 1] : 0) + (i < n - 1 && dp2[i + 1] > 0 ? dp2[i + 1] : 0) + x);
        }

        cout << res << endl;
    }

    return 0;
}

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-->0) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }

            int[] dp1 = new int[n];
            dp1[0] = a[0];
            int res = Integer.MIN_VALUE;
            for (int i = 1; i < n; i++) {
                dp1[i] = Math.max(dp1[i-1] + a[i], a[i]);
                res = Math.max(res, dp1[i]);
            }

            int[] dp2 = new int[n];
            dp2[n - 1] = a[n - 1];

            for (int i = n - 2; i>= 0 ; i--) {
                dp2[i] = Math.max(dp2[i+1] + a[i], a[i]);
            }

            for (int i = 0 ; i < n ; i++) {
                // i==0
                res = Math.max(res, (i> 0 && dp1[i-1] > 0 ? dp1[i-1] : 0) + (i < n - 1 && dp2[i+1] > 0 ? dp2[i+1]: 0) + x);
            }

            System.out.println(res);
        }
    }

}

Python

def main():

    index = 0
    t = int(input())
    index += 1

    results = []

    while t > 0:
        t -= 1
        n,x = map(int, input().split())
        index += 2

        a = list(map(int, input().split()))
        index += n

        dp1 = [0] * n
        dp1[0] = a[0]
        res = float('-inf')
        for i in range(1, n):
            dp1[i] = max(dp1[i - 1] + a[i], a[i])
            res = max(res, dp1[i])

        dp2 = [0] * n
        dp2[n - 1] = a[n - 1]
        for i in range(n - 2, -1, -1):
            dp2[i] = max(dp2[i + 1] + a[i], a[i])

        for i in range(n):
            res = max(res, (dp1[i - 1] if i > 0 and dp1[i - 1] > 0 else 0) + (
                dp2[i + 1] if i < n - 1 and dp2[i + 1] > 0 else 0) + x)

        results.append(res)

    for result in results:
        print(result)


if __name__ == "__main__":
    main()

六、常见陷阱

1. Base case容易定义错，需要考虑清楚dp状态的含义。

2. 部分题目的状态定义F[i]中的i并不是下标，而是第i个数字，这样初始化会比较方便。