草庐IT

LC-1027. 最长等差数列（动态规划）

Miraclo_acc 2023-10-15 原文

1027. 最长等差数列

难度中等237

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：

输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：

  • 2 <= nums.length <= 1000
  • 0 <= nums[i] <= 500

题解：https://leetcode.cn/problems/longest-arithmetic-subsequence/solution/zui-chang-deng-chai-shu-lie-by-zai-jian-u21ci/

状态定义：dp[i][d]: 表示以数组下标 i 处的元素结尾、公差为 d 的等差数列的最大长度。

等差数列至少包含 2 个数，也就是说 1 个数不能构成等差数列，任意 2 个元素都能构成长度为 2 的等差数列。

假设现在有一个子序列元素 x ， y，它是一个等差数列, 公差为 d，考虑 z 能否加入到 y 后面？

如果 z 能加入，意味着 z-y=y-x, 还可以是 z-d=y。

我们是从小到大推导 dp 的，我们在计算 dp[k][] 时,dp[0…k-1][] 已经计算过了，那么 dp[k][] 能否从子问题推导过来呐？ 可以的。

  • dp[i][d] = max(dp[i][d], dp[j][d] + 1), 0 <= j < i
class Solution {
    /**
        dp[i][d]:表示第i个数，与前面的数以差为d时，能构成的最长等差数列长度。
        dp[i][d] = max(dp[i][d], dp[j][d] + 1), 0 <= j < i
     */
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int[][] dp = new int[n][1010];
        for(int i = 0; i < n; i++) Arrays.fill(dp[i], 1);
        for(int i = 0; i < n; i++){
            for(int j = i-1; j >= 0; j--){
                // 表示 nums[i] 与 nums[j] 以差为 d 构成等差数列
                int d = nums[i] - nums[j] + 500;// 统一加偏移量，使下标非负
                // dp[i][d]表示：nums[i]以差为d能与前面的数构成的等差数列的长度
                dp[i][d] = Math.max(dp[i][d], dp[j][d] + 1);
                ans = Math.max(ans, dp[i][d]);
            }
        }
        return ans;
    }
}

将初始化后移：

状态转移方程有了，现在我们考虑 basecase，也就是初始化的问题，我们需要两层 for 循环给所有 dp[i][j]初始化为 1

  • 初始化完了就可进行计算再返回结果，另外比较特殊的是，由于是统一初始化成相同的值，“地位平等”，使得也可以不用先初始化，在没有显式的初始化的基础上，算完之后，再将结果 +1，也能得到相同的结果，并且后者效率高于前者（后者相较于前者少了 2 层 for 循环的时间）
class Solution {
    /**
        dp[i][d]:表示第i个数，与前面的数以差为d时，能构成的最长等差数列长度。
        dp[i][d] = max(dp[i][d], dp[j][d] + 1), 0 <= j < i
     */
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int[][] dp = new int[n][1010];
        for(int i = 0; i < n; i++){
            for(int j = i-1; j >= 0; j--){
                // 表示 nums[i] 与 nums[j] 以差为 d 构成等差数列
                int d = nums[i] - nums[j] + 500;
                // dp[i][d]表示：nums[i]以差为d能与前面的数构成的等差数列的长度
                dp[i][d] = Math.max(dp[i][d], dp[j][d] + 1);
                ans = Math.max(ans, dp[i][d]);
            }
        }
        return ans + 1;
    }
}
等差1027spanclasstoken动态规划算法leetcode

有关LC-1027. 最长等差数列（动态规划）的更多相关文章

  1. LC滤波器设计学习笔记（一）滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称

  2. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  3. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  4. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  5. ruby - 在 Ruby 中动态生成多维数组 - 2

    我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]

  6. ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2

    如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail

  7. ruby - 动态方法链？ - 2

    如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210

  8. ruby - 如何使用 method_missing 动态声明方法？ - 2

    我有一个ruby​​程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method

  9. ruby - 动态扩展现有方法或覆盖 ruby​​ 中的发送方法 - 2

    假设我们有A、B、C类。Adefself.inherited(sub)#metaprogramminggoeshere#takeclassthathasjustinheritedclassA#andforfooclassesinjectprepare_foo()as#firstlineofmethodthenrunrestofthecodeenddefprepare_foo#=>prepare_foo()neededhere#somecodeendendBprepare_foo()neededhere#somecodeendend如您所见，我正在尝试将foo_prepare()调用注入

  10. ruby - 使用 jbuilder 创建具有动态哈希键的 JSON - 2

    这里我想输出带有动态组名的json而不是单词组@tickets.eachdo|group,v|json.group{json.array!vdo|ticket|json.partial!'tickets/ticket',ticket:ticketend}end@ticket是这样的散列{a:[....],b:[.....]}我想要这样的输出{a:[.....],b:[....]} 最佳答案 感谢@AntarrByrd，这个问题有类似的答案:JBuilderdynamickeysformodelattributes使用上面的逻辑我已经

随机推荐