首页 > 其他分享 >动态规划

动态规划

时间:2024-11-05 21:24:36浏览次数:3  
标签:pre f1 nums int sum ans 动态 规划

1.打家劫舍

题目:打家劫舍

滚动变量节省空间;

因为不能连续取值,递推公式:当前最大值=max(上一个,上上一个 + 当前值)

class Solution {
public:
    int rob(vector<int>& nums) {
        int f0 = 0, f1 = 0;
        for (int x : nums) {
            int new_f = max(f1, f0 + x);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }
};

2.最大子数组和

题目:最大子数组和

求一个数组中,和最大的子数组。一种是前缀和:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        int min_pre_sum = 0;
        int pre_sum = 0;
        for (int x : nums) {
            pre_sum += x; // 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum); // 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum); // 维护前缀和的最小值
        }
        return ans;
    }
};

一种是动规:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN; // 注意答案可以是负数,不能初始化成 0
        int f = 0;
        for (int x : nums) {
            f = max(f, 0) + x;
            ans = max(ans, f);
        }
        return ans;
    }
};

标签:pre,f1,nums,int,sum,ans,动态,规划
From: https://www.cnblogs.com/Amroning/p/18528868

相关文章

  • 静态库、动态库、framework、xcframework、use_frameworks!的作用、关联核心SDK工程和
    1.1库的概念库:程序代码的集合,编译好的二进制文件加上头文件供使用,共享程序代码的一种方式。1.2库的分类根据开源情况分为:开源库(能看到具体实现)、闭源库(只公开调用的的接口,是编译后的二进制文件,看不到具体实现,使用时链接即可。)闭源库分为:动态库.td(之前叫.dylib)或.framework......
  • Nop入门: 动态SQL管理
    Nop平台提供了类似MyBatis的动态SQL管理能力,但是功能特性远比MyBatis丰富、强大。同时它的实现反而更加简单,在NopORM的基础上实现SqlLibManager只需要300多行的代码。一.使用说明1.1增加一个sql-lib.xml文件<!--/nop/demo/sql/demo.sql-lib.xml--><sql-libx:schema......
  • 基于 EventBridge + DashVector 打造 RAG 全链路动态语义检索能力
    作者:肯梦本文将演示如何使用事件总线(EventBridge),向量检索服务(DashVector),函数计算(FunctionCompute)结合灵积模型服务[1]上的EmbeddingAPI[2],来从0到1构建基于文本索引的构建+向量检索基础上的语义搜索能力。具体来说,我们将基于OSS文本文档动态插入数据,进行实时的文本......
  • MyBatis 动态 SQL 详解
    动态SQL简介动态SQL是MyBatis的强大特性之一,它允许在XML映射文件内以标签的形式编写动态SQL,完成逻辑判断和动态拼接SQL的功能。动态SQL可以根据用户输入或外部条件动态地构建查询,避免了硬编码查询逻辑,简化了数据库查询的复杂度,同时提高了代码的可读性和维护性。......
  • 戳气球 动态规划
    有n个气球,编号为0到n-1,每个气球上都标有一个数字,这些数字存在数组nums中。现在要求戳破所有的气球。戳破第i个气球,可以获得nums[i-1]*nums[i]*nums[i+1]枚硬币。这里的i-1和i+1代表和i相邻的两个气球的序号。如果i-1或i+1超出了数组的边界,......
  • 如何解决传统能源企业后备人才不足、人才规划缺失问题
    如何解决传统能源企业后备人才不足、人才规划缺失问题很多传统能源企业都面临着老员工逐渐退休,新员工还没有培养起来的问题,缺乏提前对人力资源规划的意识,导致当企业要开展新业务时或者老员工离职的时候,缺乏合适的人选。特别是对于国有企业来说,人才全流程管理体系化不足,导致员......
  • 动态生成表-判断表是否存在性能对比
    SHOWTABLESLIKE查询直接使用SHOWTABLESLIKE'table_name'来判断表是否存在。结果为空表示表不存在。$tableName='your_table_name';$res=Db::query("SHOWTABLESLIKE'{$tableName}'");if(empty($res)){echo"表不存在";}else{......
  • 73页满分PPT | 智能制造-供应链管理战略项目规划方案书
    这份PPT是一份全面的智能制造与供应链管理战略项目规划方案书,涵盖了企业C2M策略、供应链战略及现状认识、项目总体思路与需求理解、项目实施方案与交付成果,以及综合项目实施计划等多个方面,旨在通过智能化和信息化手段,实现供应链的优化和管理效率的提升,以支持企业的服务导向和多......
  • 算法笔记:Day-09(初始动态规划)
    509.斐波那契数斐波那契数(通常用F(n)表示)形成的序列称为斐波那契数列。该数列由0和1开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1)=1F(n)=F(n-1)+F(n-2),其中n>1给定n,请计算F(n)。示例1:输入:n=2输出:1解释:F(2)=F(1)......
  • 动态内存分配
    一、为什么要有动态内存分配二、malloc和free栈区中的数据出了作用域就会销毁;而静态区中数据的生命周期与全局变量一致,出了作用域也不会被销毁,直至程序结束后才会销毁。malloc函数与free函数需要包含的头文件是<stdlib.h>①malloc②free#include<stdio.h>#includ......