草庐IT

线性DP题目汇总(持续更新)

sheep.ice 2024-02-25 原文

一、前言

此篇章主要整理一些关于线性dp的题目，很多题目其实都可以被挂上线性dp的标志，比如最熟悉的最长上升子序列啊，最长公共子序列啊等等，并且线性dp在自己写力扣周赛的题目的时候，真的会时不时出几道，然后刚好利用这些题目加上dp分析的方法，把题目好好写一写。

二、题目汇总

①力扣2369.检查数组是否存在有效的划分

(1)题目描述

(2)dp分析

状态转移方程：
f [ i ] = O r { f [ i − 2 ] , i ≥ 2 & & n u m [ i − 1 ] = n u m [ i − 2 ] f [ i − 3 ] , i > = 3 & & n u m [ i − 1 ] = n u m [ i − 1 ] = n u m [ i − 2 ] f [ i − 3 ] , i > = 3 & & n u m [ i − 1 ] − n u m [ i − 2 ] = n u m [ i − 2 ] − n u m [ i − 3 ] = = 1 f[i]=Or \begin{cases} f[i-2], i\ge2\&\&num[i-1]=num[i-2] \\\\ f[i-3],i>=3\&\&num[i-1]=num[i-1]=num[i-2] \\\\ f[i-3],i>=3\&\&num[i-1]-num[i-2]=num[i-2]-num[i-3]==1 \end{cases} f[i]=Or⎩ ⎨ ⎧​f[i−2],i≥2&&num[i−1]=num[i−2]f[i−3],i>=3&&num[i−1]=num[i−1]=num[i−2]f[i−3],i>=3&&num[i−1]−num[i−2]=num[i−2]−num[i−3]==1​
这个状态转移代表什么呢?

其实就是说，当我们选择第i个数的时候，如果在第 i − 2 i-2 i−2或者第 i − 3 i-3 i−3个数字前的划分都是正确的，那么我们选择i个数，满足三个条件中的时候，我们就可以有一个合理的划分。举一个例子，假设我们的数组是 [ 1 , 1 , 1 , 2 , 3 ] [1,1,1,2,3] [1,1,1,2,3],不难发现，对于1这个数字来说，划分有两种，既可以有前两个1组成一组，也可以是前3个1，因此 f ( 2 ) , f ( 3 ) f(2),f(3) f(2),f(3)都是True,而我们在i等于5的时候，我们此时就可以利用条件3，发现是递增的，那么我们在推导的时候， f ( 5 ) ∣ ∣ f ( 5 − 3 ) = T r u e f(5) || f(5-3)=True f(5)∣∣f(5−3)=True,因此最终是可以成功划分的。

状态初始化

f [ 0 ] = t r u e , f [ 1 ] = f a l s e f[0]=true, f[1]=false f[0]=true,f[1]=false

因为第0个划分不需要划分也是正确的，这个也是推出其他是否正确的一个必要条件。

最终结果: f [ n ] f[n] f[n]

时间复杂度: O ( N ) O(N) O(N)

(3)完整AC代码

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<bool> f(n + 1, false);
        f[0] = true;

        for(int i = 2; i <= n; i ++ ) {
            if(nums[i - 1] == nums[i - 2]) f[i] = f[i] || f[i - 2];
            if(i >= 3) {
                if(nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3])
                    f[i] = f[i] || f[i - 3];
                if(nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1)
                    f[i] = f[i] || f[i - 3];
            }
        }

        return f[n];
    }
};

②力扣2370.最长理想子数组

(1)题目描述

(2)dp分析

状态转移方程:
f ( i , j ) = m a x { f ( i − 1 , j ) , 不选择第 i 个字符的情况 f ( i − 1 , [ m a x ( j − k , 0 ) , m i n ( j + k , 25 ) ] ) , 选择第 i 个字符的情况 f(i,j)=max \begin{cases} f(i-1,j),不选择第i个字符的情况 \\\\ f(i-1,[max(j-k,0),min(j+k,25)]),选择第i个字符的情况 \end{cases} f(i,j)=max⎩ ⎨ ⎧​f(i−1,j),不选择第i个字符的情况f(i−1,[max(j−k,0),min(j+k,25)]),选择第i个字符的情况​
相关分析:

这个转移和最长上升子序列的那个dp非常的像，所以也就告诉我们，这个题目其实可以利用一维进行dp，当然下面的代码也会展现出二维的代码，就是二维的比较蛋疼，因为，每一层转移的时候，都需要把所有字符在上一层的状态迁移到本层，最终得到的结果才可以在最后一层里面推出来。

最终结果: m a x ( f [ n ] [ i ] , 0 ≤ i ≤ 25 ) max(f[n][i], 0\leq i \leq 25) max(f[n][i],0≤i≤25)

时间复杂度: O ( n ∗ ( 26 + 2 ∗ k ) ) O(n*(26 + 2 * k)) O(n∗(26+2∗k))

(3)完整AC代码

//二维代码
class Solution {
public:
    int longestIdealString(string s, int k) {
        int n = s.size();
        int f[100050][26];
        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 0; j < 26; j ++ ) f[i][j] = f[i - 1][j];
            int j = s[i - 1] - 'a';
            for(int p = max(j - k, 0); p <= min(j + k, 25); p ++ ) {
                f[i][j] = max(f[i][j], f[i - 1][p] + 1);
            } 
        }
        int maxn = 0;
        for(int i = 0; i < 26; i ++ ) {
            maxn = max(maxn, f[n][i]);
        }

        return maxn;
    }
};

//一维代码
class Solution {
public:
    int longestIdealString(string s, int k) {
        vector<int> f(26, 0);
        for(auto c : s) {
            int j = c - 'a';
            f[j] = f[j] + 1;
            for(int i = max(0, j - k); i <= min(25, j + k); i ++ ) {
                if(i != j) f[j] = max(f[j], f[i] + 1);
            }
        }
        int maxn = 0;
        for(auto t : f) maxn = max(t, maxn);
        return maxn;
    }
};
汇总题目spanclassstyle算法动态规划线性dp刷题dp分析

有关线性DP题目汇总(持续更新)的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2

    我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它​​不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数

  3. jenkins部署1--jenkins+gitee持续集成 - 2

    前置步骤我们都操作完了，这篇开始介绍jenkins的集成。话不多说，看操作1、登录进入jenkins后会让你选择安装插件，选择第一个默认的就行。安装完成后设置账号密码，重新登录。2、配置JDK和Git都需要执行路径，所以需要先把执行路径找到，先进入服务器的docker容器，2.1JDK的路径root@69eef9ee86cf:/usr/bin#echo$JAVA_HOME/usr/local/openjdk-82.2Git的路径root@69eef9ee86cf:/#whichgit/usr/bin/git3、先配置JDK和Git。点击：ManageJenkins>>GlobalToolCon

  4. objective-c - 在设置 Cocoa Pods 和安装 Ruby 更新时出错 - 2

    我正在尝试为我的iOS应用程序设置cocoapods但是当我执行命令时:sudogemupdate--system我收到错误消息:当前已安装最新版本。中止。当我进入cocoapods的下一步时:sudogeminstallcocoapods我在MacOS10.8.5上遇到错误:ERROR:Errorinstallingcocoapods:cocoapods-trunkrequiresRubyversion>=2.0.0.我在MacOS10.9.4上尝试了同样的操作，但出现错误:ERROR:Couldnotfindavalidgem'cocoapods'(>=0),hereiswhy:U

  5. ruby-on-rails - Rails Associations 的更新方法是什么？ - 2

    这太简单了，太荒谬了，我在任何地方都找不到关于它的任何信息，包括API文档和Rails源代码:我有一个:belongs_to关联，我开始理解当您没有关联时您在Controller中调用的正常模型方法与您有关联时调用的方法略有不同。例如，我的关联在创建Controller操作时运行良好:@user=current_user@building=Building.new(params[:building])respond_todo|format|if@user.buildings.create(params[:building])#etcetera但我找不到关于更新如何工作的文档:@user

  6. ruby-on-rails - OSX Yosemite 更新破坏了 pow.cx - 2

    升级到OSXYosemite后，我现有的pow.cx安装不起作用。升级到最新的pow.cx无效。通过事件监视器重新启动它也没有成功。 最佳答案 卸载(!)并重新安装解决了这个问题。curlget.pow.cx/uninstall.sh|shcurlget.pow.cx|sh 关于ruby-on-rails-OSXYosemite更新破坏了pow.cx，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/q

  7. ruby - 将 Gitlab 从 9.3.7 更新到 9.3.8 安装 re2 时出错 - 2

    我们在Ubuntu14.04和Gitlab9.3.7上运行，运行良好。我们正在尝试更新到Gitlabv9.3.8的最新安全补丁，但它给我们这个错误:Gem::Ext::BuildError:ERROR:Failedtobuildgemnativeextension.currentdirectory:/home/git/gitlab/vendor/bundle/ruby/2.3.0/gems/re2-1.0.0/ext/re2/usr/local/bin/ruby-r./siteconf20170720-19622-15i0edf.rbextconf.rbcheckingformain(

  8. ruby - Sinatra session 未按预期持续 - 2

    我正在尝试使用Sinatra中的重定向和session在网站周围传递一些数据。这是一个简化的示例，使用PrettyPrint进行调试:require'pp'require'rubygems'require'sinatra'enable:sessionsget'/'dosession[:foo]='12345'puts'session1'ppsessionredirectto('/redir')endget'/redir'doputs'session2'ppsession'helloworld'end查看Thin的输出，我看到:>>Listeningon0.0.0.0:4567,CTRL

  9. ruby-on-rails - Rails 更新属性 - 2

    我遇到了以下问题。我有一个名为user的模型，它有一个名为activated的列。我试图通过激活的方法更新该值？但它给我错误:验证失败:密码不能为空，密码太短(最少6个字符)这对我来说没有意义，因为我没有接触密码字段!我只想更新激活的列。我把我认为相关的代码放在这里，但如果你认为你需要更多，请问:)非常感谢您!型号:attr_accessor:passwordattr_accessible:name,:email,:password,:password_confirmation,:activatedhas_many:sucu_votesemail_regex=/\A[\w+\-.]+@

  10. ruby-on-rails - 如果存在则更新，否则什么也不做？ - 2

    当且仅当模型存在时，我才尝试更新模型的值。如果没有，我什么都不做。搜索似乎只返回更新或创建问题/答案，但我不想创建。我知道我可以用一个简单的方法来做到这一点:found=Model.find_by_id(id)iffoundupdatestuffend但是，我觉得有一种方法可以在一次调用中完成此操作，而无需分配任何临时本地值或执行if。如果记录不存在，我该如何编写一个Rails调用来更新记录而不出现嘈杂错误？最新的Rails3.x 最佳答案 您可以使用try在对find_by_id或where的结果调用update_attribut

随机推荐