草庐IT

动态规划详解（完结篇）——如何抽象出动态规划算法？以及解题思路

饮水思源的美西螈 2024-02-05 原文

今天直接开始讲解

FIRST：如何抽象出动态规划算法？

这个问题，困扰了无数代OIER，包括本蒟蒻

在比赛的时候，看一道题，怎么想到他是什么算法的呢？

这就需要抽象能力

而不同的算法，往往有着不同的特点

就来说说动态规划的题目特点

  1. 通过遍历，能够把所有的情况考虑到。这一点同样适合于递归

  1. 有可能存在重叠性的子问题。没错，这一点也适用于递归

有的同学就问了

那动态规划和递归不是同样的特点吗？

回到蒟蒻写的动态规划1

里面说过，动态规划是可以用递归代替的

也就是说，如果你的状态转移方程真的实在绞尽脑汁费劲九牛二虎之力也想不出来，就用递归来做

但代价就是也许拿不到满分

SECOND：解题思路

动态规划抽象出状态之后，就要进行遍历每一个状态

  1. 抽象状态

  1. 初始化

  1. 确定循环起始以及边界

  1. 写出状态转移方程

  1. 输出

  1. return 0;

大概就是上述这个过程了

每日例题：

题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 22 个整数 � T（1≤�≤10001≤ T≤1000）和 � M（1≤�≤1001≤ M≤100），用一个空格隔开，� T 代表总共能够用来采药的时间，� M 代表山洞里的草药的数目。
接下来的 � M 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1复制
70 3 71 100 69 1 1 2
输出 #1复制
3
说明/提示
【数据范围】
对于 30%30% 的数据，�≤10 M≤10；
对于全部的数据，�≤100 M≤100。

一个纯纯的01背包模板

  1. 抽象状态：f[i]表示第i分钟采到的最大价值

  1. 初始化：no

  1. 确定循环起始以及边界：第一层循环1到m，第二层循环t到0（真的是01背包模板，看不懂的可以借鉴一下上一篇文章）

  1. 写出状态转移方程：dp[j]=max(dp[j-w[i]]+val[i], dp[j]);如果采了这个药，那么就要用当前时间减去采药的时间，也就是采药之前需要的时间加上现在的状态

  1. 输出（见代码）

真正做题时，大家也可以按照这个顺序，非常的清晰

那么有的同学就要问了：状态定义有什么规律吗？

  1. 首先，我们先创建一个数组，f数组，假设他是一维的，然后去想这个一维状态表示什么（简单多了）

  1. 就假设是一维，尝试写状态转移方程

  1. 如果发现，写不通了，也就是有更多的情况表示不出来

  1. 增加维度

然后循环上述操作

但是遇到很难的题，还得是靠智商，因为难的动态规划不仅仅要抽象出来

更需要你优化，也就是减少维度

来迟的AC代码：


# include <iostream>
# include <cstdio>
using namespace std;
int w[105], val[105];
int dp[1005];
int main(){
    int t,m;    
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&w[i],&val[i]);
    }
    for(int i=1;i<=m;i++) {
        for(int j=t;j>=0;j--) {
            if(j>=w[i]){
                dp[j]=max(dp[j-w[i]]+val[i], dp[j]);
            }
        }
    }    
    printf("%d",dp[t]);
    return 0;
}

这会动态规划系列就真的结束了

这次讲算法比之前真的费了更大的力气，更多的时间，更多的键盘（）

所以希望各位佬能够点个免费的赞

如果动态规划方面还有什么不明白的，随时私信我

我可以出番外篇（）

这篇文章到这里就结束了

再见

mdash解题stylexffxff0cc++算法动态规划数据结构图论

有关动态规划详解（完结篇）——如何抽象出动态规划算法？以及解题思路的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  4. 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

  5. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  6. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  7. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  8. ruby - 如何指定 Rack 处理程序 - 2

    Rackup通过Rack的默认处理程序成功运行任何Rack应用程序。例如:classRackAppdefcall(environment)['200',{'Content-Type'=>'text/html'},["Helloworld"]]endendrunRackApp.new但是当最后一行更改为使用Rack的内置CGI处理程序时，rackup给出“NoMethodErrorat/undefinedmethod`call'fornil:NilClass”:Rack::Handler::CGI.runRackApp.newRack的其他内置处理程序也提出了同样的反对意见。例如Rack

  9. ruby - 如何每月在 Heroku 运行一次 Scheduler 插件？ - 2

    在选择我想要运行操作的频率时，唯一的选项是“每天”、“每小时”和“每10分钟”。谢谢!我想为我的Rails3.1应用程序运行调度程序。 最佳答案 这不是一个优雅的解决方案，但您可以安排它每天运行，并在实际开始工作之前检查日期是否为当月的第一天。 关于ruby-如何每月在Heroku运行一次Scheduler插件？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/8692687/

  10. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

随机推荐