蓝桥杯_day6

不同路径

【题目描述】
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

【输入样例】

m=3 n=7

【输出样例】

28

【数据规模与约定】

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

【解题思路】
创建一个二维的dp表，
通过题目我们可以得出，dp[i][j]的值表示的是到达当前位置一共有多少条不同的路径。
在初始化的时候，因为题目限制在走动的时候只能往右或者往下，不能回退，所以我们会发现第一行和第一列都是1，在初始化的时候可以先将第一行以及第一列都初始化为1.

【C++程序代码】
方法一：初始化一行一列

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = 1;
        for (int i = 1; i < m; i++)
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++)
        {
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
};

方法二：创建虚拟一行一列

class Solution {
public:
    int uniquePaths(int m, int n) {
        int row = m + 1;
        int line = n + 1;
        vector<vector<int>> dp(row, vector<int>(line));

        dp[0][1] = 1;

        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j < line; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};

不同路径II

【题目描述】
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

【输入样例】

obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

【输出样例】

2

【数据规模与约定】

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

【解题思路】
创建一个二维的dp表，
通过题目我们可以得出，dp[i][j]的值表示的是到达当前位置一共有多少条不同的路径。
在初始化的时候，因为题目限制在走动的时候只能往右或者往下，不能回退，所以我们会发现第一行和第一列都是1，在初始化的时候可以先将第一行以及第一列都初始化为1.

【C++程序代码】

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int row = obstacleGrid.size() + 1;
        int col = obstacleGrid[0].size() + 1;

        vector<vector<int>> dp(row, vector<int>(col));
        dp[0][1] = 1;

        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j < col; j++)
            {
                if (obstacleGrid[i - 1][j - 1] != 1)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[row - 1][col - 1];
    }
};

拿金币

【题目描述】
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

【输入格式】
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。

【输出格式】
最多能拿金币数量。

【输入样例】

3  
1 3 3  
2 2 2  
3 1 2

【输出样例】

11

【数据规模与约定】

• n<=1000

【解题思路】
每经过一个格子对这个位置的左侧和上面进行比较，选择大的金币数量和当前所处于的格子的金币数量进行相加。

【C++程序代码】

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> s(n, vector<int>(n));

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

	vector<vector<int>> dp(n+1, vector<int>(n+1));


	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + s[i - 1][j - 1];
		}
	}
	
	return 0;
}

珠宝的最高价值

【题目描述】
现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取
  注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

【输入样例】

frame = [[1,3,1],[1,5,1],[4,2,1]]

【输出样例】

12

【数据规模与约定】

• 0 < frame.length <= 200
• 0 < frame[0].length <= 200

【解题思路】
这一题基本与上题相同。
每经过一个格子对这个位置的左侧和上面进行比较，选择大的珠宝价格和当前所处于的格子的珠宝价格进行相加。

【C++程序代码】

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int row = frame.size();
        int col = frame[0].size();

        vector<vector<int> > dp(row + 1, vector<int>(col + 1));
		for (int i = 1; i <= row; i++)
		{
			for (int j = 1; j <= col; j++)
			{
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + frame[i - 1][j - 1];
			}
		}
		return dp[row][col];
    }
};