算法实验二矩阵最小路径和 LIS-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法实验二矩阵最小路径和 LIS。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法实验课二

矩阵最小路径和

leetcode裸题

最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

算法实验二矩阵最小路径和 LIS,算法,动态规划

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

class Solution {
public:
    //dp[i][j]代表该位置上的最小和
    //dp[i][j] = dp[i-1][j]) if(grid[i-1][j] > )
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();//行数
        int n = grid[0].size();//列数

        vector<vector<int>> dp = grid;
        for(int i = 1; i < m; i ++)
            dp[i][0] = dp[i][0] + dp[i - 1][0];
        
        for(int j = 1; j < n; j ++)
            dp[0][j] = dp[0][j] + dp[0][j - 1];
        
        for(int i = 1; i < m; i ++)
        {
            for(int j = 1; j < n; j ++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + dp[i][j];
                // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
};

完整实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
LL dp[N][N];
LL grid[N][N];
int n, m;

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
		{
			cin >> grid[i][j];
			dp[i][j] = grid[i][j];//初始化
		}
	for(int i = 1; i <= n; i ++)
		dp[i][1] = dp[i][1] + dp[i - 1][1];
	
	for(int j = 1; j <= m; j ++)
		dp[1][j] = dp[1][j] + dp[1][j - 1];
		 
	for(int i = 2; i <= n; i ++)
	{
		for(int j = 2; j <= m; j ++)
		{
			dp[i][j] += min(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	
	cout << dp[n][m] << endl;
	
	return 0;
}

LIS最长上升子序列

算法实验二矩阵最小路径和 LIS,算法,动态规划

题目练习

1.蓝桥勇士

#include <bits/stdc++.h>
using namespace std;
const int N = 2550;
int dp[N];//表示以a[i]结尾的最长上升子序列的长度
int a[N];
int n;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        dp[i] = 1;//初始化
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);//状态转移方程

    int res = -0x3f3f3f3f;//答案初始为一个最小值
    for(int i = 1; i <= n; i ++)//判断以哪个a[i]结尾是最长的上升子序列
        res = max(res, dp[i]);
    
    cout << res << endl;
    return 0;
}

判断以哪个a[i]结尾是最长的上升子序列可以偷懒使用库函数

// int res = -0x3f3f3f3f;//答案初始为一个最小值 // for(int i = 1; i <= n; i ++)//判断以哪个a[i]结尾是最长的上升子序列 // res = max(res, dp[i]);

cout << *max_element(dp + 1, dp + 1 + n) << endl;

以上最长上升子序列（LIS）算法时间复杂度O（n^2）

还有一种实现方式，可以利用二分实现O（nlogn）的时间复杂度

题目二

1.合唱队形

算法实验二矩阵最小路径和 LIS,算法,动态规划

代码：文章来源地址https://www.toymoban.com/news/detail-852048.html

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N], dp1[N], dp2[N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        dp1[i] = 1;
        dp2[i] = 1;
    }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                dp1[i] = max(dp1[i], dp1[j] + 1);
    
    for(int i = n; i ; i --)
        for(int j = n; j > i; j --)
            if(a[j] < a[i])
                dp2[i] = max(dp2[i], dp2[j] + 1);
    
    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++)
        res = max(res, dp1[i] + dp2[i] - 1);
    
    cout << n - res << endl;
    return 0;
}

leetcode裸题

300. 最长递增子序列 - 力扣（LeetCode）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[2550];
        if(nums.size() == 0)
            return 0;
        for(int i = 0; i < nums.size(); i ++)
        {
            dp[i] = 1;//初始化
            for(int j = 0; j < i; j ++)
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
        }

        return *max_element(dp, dp + nums.size());

    }
};

到了这里，关于算法实验二矩阵最小路径和 LIS的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！