目录
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好动态规划，应对 “DP杯”。
事不宜迟，我们即刻开始刷题！
一个楼梯共有 n 级台阶，每次可以走一级或者两级，
问从第 0 级台阶走到第 n 级台阶一共有多少种方案。
共一行，包含一个整数 n。
共一行，包含一个整数，表示方案数。
1 ≤ n ≤ 15
58这道题是一道经典的dp入门题目，
我打算使用三种方法去做，层层推进，一起入门递归：
这道题在之前dfs的刷题中也有出现，
我们可以用dfs搜索所有的方案:
跳三级台阶就是跳两级台阶的方法+跳一级台阶的方法；
跳四级台阶就是跳三级台阶的方法+跳二级台阶的方法；
以此类推：
最后得出答案：
代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int dfs(int u)
{
if(u == 1) return 1;
else if(u == 2) return 2;
return dfs(u - 1) + dfs(u - 2);
}
int main()
{
scanf("%d", &n);
int res = dfs(n);
printf("%d", res);
return 0;
}
实际上第一种方法的时间复杂度太高，
有2的n次方那么大：
如果n >= 42，就会超时：
为了减少时间的消耗，我们可以用记忆化搜索：
将已经求过的值记录到一个数组中，
这样搜索过的值就不用重复搜索：
下面是代码实现：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int sum = 0;
const int N = 30;
int mem[N];//用一个数组记录
int dfs(int u)
{
if(mem[u]) return mem[u];//如果记录过，就不用往下搜索了
if(u == 1) return 1;
else if(u == 2) return 2;
else sum = dfs(u - 1) + dfs(u - 2);
mem[u] = sum;//将该位置的值记录进数组
return mem[u];
}
int main()
{
scanf("%d", &n);
int res = dfs(n);
printf("%d", res);
return 0;
}
我们发现这样之后，就算n = 100，也只需要1ms：
我们发现，其实这道题动态规划的
状态表达式就是由暴力搜索推出来的，
递归搜索是从上往下搜索，
再从下往上回溯，
其实得出的结果的过程就是在回溯的时候：
那我们可以不用搜索这个过程，直接从下往上递推，
这就是动态规划：
下面是代码实现：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
const int N = 30;
int fib[N];
int main()
{
scanf("%d", &n);
fib[1] = 1;
fib[2] = 2;
if(n == 1 || n == 2)
{
printf("%d", fib[n]);
return 0;
}
for(int i = 3; i <= n; i++)
{
//这个就是动态规划的状态表达式
fib[i] = fib[i - 1] + fib[i - 2];
}
printf("%d", fib[n]);
return 0;
}
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称
@作者:SYFStrive @博客首页:HomePage📜：微信小程序📌：个人社区（欢迎大佬们加入）👉：社区链接🔗📌：觉得文章不错可以点点关注👉：专栏连接🔗💃：感谢支持,学累了可以先看小段由小胖给大家带来的街舞👉微信小程序（🔥）目录自定义组件-behaviors 1、什么是behaviors 2、behaviors的工作方式 3、创建behavior 4、导入并使用behavior 5、behavior中所有可用的节点 6、同名字段的覆盖和组合规则总结最后自定义组件-behaviors 1、什么是behaviorsbehaviors是小程序中，用于实现
遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg
ES一、简介1、ElasticStackES技术栈：ElasticSearch：存数据+搜索；QL；Kibana：Web可视化平台，分析。LogStash：日志收集，Log4j:产生日志；log.info(xxx)。。。。使用场景：metrics：指标监控…2、基本概念Index（索引）动词：保存（插入）名词：类似MySQL数据库，给数据Type（类型）已废弃，以前类似MySQL的表现在用索引对数据分类Document（文档）真正要保存的一个JSON数据{name:"tcx"}二、入门实战{"name":"DESKTOP-1TSVGKG","cluster_name":"elasticsear
有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.
我想在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
首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟
我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]
如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail
如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希: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