[Algorithm][综合训练][合唱团][跳台阶扩展问题][矩阵最长递增路径]详细讲解

本文主要是介绍[Algorithm][综合训练][合唱团][跳台阶扩展问题][矩阵最长递增路径]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.合唱团
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 2.跳台阶扩展问题
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 3.矩阵最长递增路径
    • 1.题目链接
    • 2.算法原理详解 && 代码实现


1.合唱团

1.题目链接

  • 合唱团

2.算法原理详解 && 代码实现

  • 解法:动态规划

    • 状态表示

      • f[i][j]:从[i, j]中挑选,挑j个人,最后一个人必选,此时的最大乘积
      • g[i][j]:从[i, j]中挑选,挑j个人,最后一个人必选,此时的最小乘积
    • 状态转移方程
      请添加图片描述

    • 返回值max(f[n][k] ~ f[k][k])

    • 初始化:绿色圆圈部分全部初始化为正负无穷,保证不会参与比较
      请添加图片描述

    #include <iostream>
    #include <vector>
    using namespace std;int main()
    {const long long INF = 0x3f3f3f3f3f3f3f3f;int n = 0, k = 0, d = 0;cin >> n;vector<int> nums(n + 1, 0);for(int i = 1; i <= n; i++){cin >> nums[i];}cin >> k >> d;vector<vector<long long>> f(n + 1, vector<long long>(k + 1, 0));vector<vector<long long>> g(n + 1, vector<long long>(k + 1, 0));     // 初始化在填表中进行for(int i = 1; i <= n; i++){g[i][1] = f[i][1] = nums[i]; // 初始化for(int j = 2; j <= min(i, k); j++) // 挑选几个人{f[i][j] = -INF; // 初始化g[i][j] = INF;  // 初始化// 前⾯挑选的最后⼀个位置for(int prev = max(i - d, j - 1); prev <= i - 1; prev++){f[i][j] = max(max(f[prev][j - 1] * nums[i], g[prev][j - 1] * nums[i]), f[i][j]);g[i][j] = min(min(f[prev][j - 1] * nums[i], g[prev][j - 1] * nums[i]), g[i][j]);}}}long long ret = -INF;for(int i = k; i <= n; i++){ret = max(ret, f[i][k]);}cout << ret << endl;return 0;
    }
    

2.跳台阶扩展问题

1.题目链接

  • 跳台阶扩展问题

2.算法原理详解 && 代码实现

  • 解法一:动态规划
  • 解法二:规律
    #include <iostream>
    using namespace std;int main()
    {int n = 0;cin >> n;cout << (1 << (n - 1)) << endl;return 0;
    }
    

3.矩阵最长递增路径

1.题目链接

  • 矩阵最长递增路径

2.算法原理详解 && 代码实现

  • 解法记忆化搜索 --> 整理下来是为了再熟悉一下记忆化搜索,无它
    class Solution 
    {int n = 0, m = 0;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};vector<vector<int>> mem;
    public:int solve(vector<vector<int>>& matrix) {n = matrix.size(), m = matrix[0].size();mem.resize(n, vector<int>(m, -1));int ret = 1;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){ret = max(ret, DFS(i, j, matrix));}}return ret;}int DFS(int i, int j, const vector<vector<int>>& matrix){if(mem[i][j] != -1){return mem[i][j];}int len = 1;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j]){len = max(len, 1 + DFS(x, y, matrix));}}mem[i][j] = len;return len;}
    };
    

这篇关于[Algorithm][综合训练][合唱团][跳台阶扩展问题][矩阵最长递增路径]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1117212

相关文章

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应