[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

相关文章

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机