首页 > 其他分享 >动态规划- leecode 122

动态规划- leecode 122

时间:2024-01-21 22:01:13浏览次数:31  
标签:int max 复杂度 122 leecode prices 动态 dp size

Problem: 122. 买卖股票的最佳时机 II

目录

思路

仍然是一道比较简单的动态规划,但是一上手做还是没理清楚状态是什么。一天的状态只有两种,持有股票和没有股票,这样就可以列出状态转移方程\(dp[i][j]=max(dp[i-1][j],dp[i-1][j*]+或-price[i])\), 这里的j表示有无股票,j*表示从另一种状态转移到这种状态

解题方法

开dp[n][2]的数组,dp[i][0]表示没有股票, dp[i][1]表示有股票,这里和背包不同的是需要注意dp[i-1][0]到dp[i][1]需要-price[i],反过来需要+price[i]

复杂度

时间复杂度:
\(O(n)\)

空间复杂度:
\(O(2n)\)

Code

//这里是第一种解法
class Solution {
public:
    int maxProfit(vector<int>& prices) {
      int n=prices.size();
      int dp[n][2];
      dp[0][0]=0;
      dp[0][1]=-prices[0];
      for (size_t i = 1; i < n; i++)
      {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
      }
      return dp[n-1][0];
    }
};

//这里稍作优化,其实可以发现动态规划中这一行的数据只和上一行有关系,所以直接省略之前的储存
class Solution {
public:
    int maxProfit(vector<int>& prices) {
      int n=prices.size();
      int precash=0,prestock=-prices[0];
      int cash=0,stock=0;
      for (size_t i = 1; i < n; i++)
      {
        cash=max(precash,prestock+prices[i]);
        stock=max(prestock,precash-prices[i]);
        precash=cash;
        prestock=stock;
      }
      return cash;
    }
};

标签:int,max,复杂度,122,leecode,prices,动态,dp,size
From: https://www.cnblogs.com/oxidationreaction/p/17978490

相关文章

  • 二维动态规划+子集和
    题目:查看代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e3+7;constllmod=1e5+7;intn,s;intdp[N][N],a[N];intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(in......
  • 模拟jdk动态代理(完整版)
    实现思路1:定义一个字符串s2:加载s利用流生成对应的java文件3:通过类加载器加载java文件生成class文件4:通过class生成代理对象5:测试成功我使用过jdk代理的场景1:通过拦截request对象,代理其中的get参数的方法来过滤敏感词2:通过阅读aop源码发现,底层用的也是动态代理(jdk,cglib)3:jdk代......
  • Qt如何调用VS编写的动态链接库(dll文件)
     下面是我在VS编译器上写的一个简单的dll文件,关于dll文件如何编写,我就不再赘述了。.h文件#ifndef_MYDLL_H#define_MYDLL_H#ifdefMYDLL_EXPORTS#defineMYDLL_API__declspec(dllexport)#else#defineMYDLL_API__declspec(dllimport)#endifextern"C"MYDLL_......
  • 动态规划--摆花(二维dp)
    #include<iostream>usingnamespacestd;//dp[i][j]表示第i种花位置,第j个位置为止longlongintdp[120][120];longlonginta[160];intmain(){intn,m;cin>>n>>m;//n种花m盆for(inti=1;i<=n;i++){cin>>a[i];}dp[0][0]=1;for(inti=1;i<=n;......
  • spring--JDK动态代理的实现原理
    JDK动态代理的实现原理涉及到Java的反射机制。它允许在运行时动态创建一个代理类,这个代理类实现了一组接口,并将所有方法调用转发到一个InvocationHandler实例。下面是JDK动态代理的实现原理的详细步骤:定义接口:首先,定义一个或多个接口,这些接口声明了需要被代理的方法。......
  • spring--CGLIB动态代理的实现原理
    CGLIB(CodeGenerationLibrary)是一个强大的、高性能、高质量的代码生成库,它可以在运行时扩展Java类和实现Java接口。CGLIB动态代理是基于继承的方式来实现的,它不需要接口,可以代理普通类。以下是CGLIB动态代理的实现原理:继承:CGLIB动态代理通过继承目标类来创建子类,并在......
  • spring--JDK动态代理和CGLIB代理的区别
    JDK动态代理和CGLIB代理是Java中常用的两种动态代理实现方式,它们各有特点和适用场景:JDK动态代理:JDK动态代理是基于接口的代理方式,它使用Java反射机制来创建代理对象,并要求目标对象实现一个或多个接口。在代理过程中,JDK动态代理会创建一个实现了目标对象所有接口的代......
  • 动态代理IP如何选择?
    IP地址是由IP协议所提供的一种统一的地址格式,通过为每一个网络和每一台主机分配逻辑地址的方式来屏蔽物理地址的差异。根据IP地址的分配方式,IP可以分为动态IP与静态IP两种。对于大部分用户而言,日常使用的IP地址均为动态IP地址。从代理IP的角度而言,大多数用户的需求也主要是动态代理......
  • 动态规划--放置油桶
    题目:题目:#include<iostream>#include<cstdio>usingnamespacestd;intn,k,dp[1000005];intmain(){scanf("%d%d",&n,&k);for(inti=1;i<=k+1;i++)dp[i]=i+1;//dp[i]表示当n=i时的答案for(inti=k+2;i<=n;i++)......
  • 深度理解 Spring 动态数据源切换是如何实现的
    更新(不是必读,只为了帮助读者更好的理解执行过程)2022-11-16结合事务TransactionInterceptor的执行,剖析数据源是如何切换的详细分析为什么,切面要设置@Order(-9999)属性针对点一回答如下在SpringBoot项目启动的时候,会去扫描所有配置类,生成一个个的Bean,被@Transaction标记的......