【算法/训练】：动态规划DP

一、路径类

1. 字母收集

思路：

1、预处理

     对输入的字符矩阵我们按照要求将其转换为数字分数，由于只能往下和往右走，因此走到（i，j）的位置要就是从（i - 1， j）往下走，或者是从(i，j  - 1)的位置往右走，由于我们要使得路程遍历积分最多，则应该从积分多的位置过来，

2、状态表示 dp[i][j] 表示：从[0, 0]出发，到底[i, j]位置，一共有多少分

3、状态转移方程

    故（i，j）位置的积分应该为dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]) + dp[ i ][ j ];

4、初始化

    但是上面仅对于（i >= 1 && j >= 1）成立，对于第一行和第一列我们应该特殊处理，利用前缀和的知识可以求得，走到第一列的第i个位置最多能拿的积分以及走到第一行的第j个位置最多能拿的积分，然后我们就可以按照dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]) + dp[ i ][ j ]的方法遍历每个节点即可

AC代码如下：

#include <iostream>
using namespace std;
 
const int N = 1005;
int dp[N][N];
 
int main() {
	int n, m;
	cin >> n >> m;
	char ch;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> ch;
			if (ch == 'l') dp[i][j] = 4;
			else if (ch == 'o') dp[i][j] = 3;
			else if (ch == 'v') dp[i][j] = 2;
			else if (ch == 'e') dp[i][j] = 1;
			else a[i][j] = 0;
		}
	}
 
for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + dp[i][0]; 
for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + dp[0][j]; 
 
	for (int i = 1; i < n; i++){
		for (int j = 1; j < m; j++){
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j];
		}
	}
 
	cout << dp[n - 1][m - 1] << endl;
	return 0;
}

2、[NOIP2002 普及组] 过河卒

图解：

思路：
1、状态表示
dp[i][j] 表示：从[0, 0]出发，到底[i, j]位置，一共有多少种方法
2、状态转移方程

    dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[i][j - 1] (i > 0 && j > 0)

当走到马可以走的地方，dp[ i ][ j ] = 0;
3、初始化

先创建一个 dp[ n + 2 ][ m + 2 ]，然后让dp[ 0 ][ 1 ] = 1 或者 dp[ 1 ][ 0 ] = 1。注意这样初始化的时候，x需要+1,y也需要+1.和dp表位置一一对应

AC代码如下：

#include <iostream>
#include <vector>
using namespace std;
 
//int dp[1005][1005];
int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    
    vector<vector<long long>> dp(n + 2, vector<long long>(m + 2));
    dp[0][1] = 1;
    x += 1, y += 1;和dp表位置一一对应
 
    for (int i = 1; i <= n + 1; i++)
    {
        for (int j = 1; j <= m + 1; j++) { //马所在位置
            if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x && j == y))
            {
                dp[i][j] == 0;
            }
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n + 1][m + 1] << endl;
 
    return 0;
}

3、礼物的最大价值

思路：
1、状态表示
dp[i][j] 表示：到[i, j]位置时礼物的最大价值
2、状态转移方程

    dp[ i ][ j ] = max(dp[ i - 1 ][ j ] + w[ i ][ j ]，dp[ i ][ j - 1] + w[ i ][ j ] ）  
3、初始化

我们应该初始化第一行第一列的值，但是我们可以选择多加第一行第一列，把其初始化为0

int maxValue(vector<vector<int> >& grid) {
	int n = grid.size(), m = grid[0].size();
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
		}
	}
	return dp[n][m];
}

二、子序列和连续序列类

1. mari和shiny

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/985744