（每日一题）字⺟收集——＜动态规划-路径问题＞

1. 题⽬链接：DP39字⺟收集

2. 题⽬描述：

3. 解法：

算法思路：

基础的路径问题的dp模型。 

 C++算法代码：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    //初始化
    int m,n;
    cin >> m >> n;
    vector<vector<char>>temp(m, vector<char>(n));   //字母矩阵
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> temp[i][j];
        }
    }
    //动态规划
    vector<vector<int>>dp(m+1, vector<int>(n+1));
    for(int i=m-1;i>=0;i--)
    {
        for(int j=n-1;j>=0;j--)
        {
            int t = 0;
            if(temp[i][j] == 'l') t = 4;
            else if(temp[i][j] == 'o') t = 3;
            else if(temp[i][j] == 'v') t = 2;
            else if(temp[i][j] == 'e') t = 1;
            dp[i][j]=max(dp[i+1][j],dp[i][j+1])+t;
        }
    }
    cout<<dp[0][0];
    return 0;
}

Java算法代码：

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息 
public class Main
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), m = in.nextInt();
		char[][] arr = new char[n + 1][m + 1];
		for (int i = 1; i <= n; i++)
		{
			char[] s = in.next().toCharArray();
			for (int j = 1; j <= m; j++)
			{
				arr[i][j] = s[j - 1];
			}
		}
		int[][] dp = new int[n + 1][m + 1];
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				int t = 0;
				if (arr[i][j] == 'l') t = 4;
				else if (arr[i][j] == 'o') t = 3;
				else if (arr[i][j] == 'v') t = 2;
				else if (arr[i][j] == 'e') t = 1;
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + t;
			}
		}
		System.out.println(dp[n][m]);
	}
}