给你一个整数数组arr，表示不同面额的硬币；以及一个整数aim，表示需要放入钱包的目标金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。
每种硬币的数量无限。
本题自然可以通过遍历所有可能的硬币组合以求得最少的硬币数量。
每次都选择三种面额（以用例1举例）中的一枚放入到钱包中，直到钱包达到目标金额。
上面这个思路其实就是深度优先搜索的方法（DFS）。递归深度就是使用的硬币的个数。
然而这种方式将会出现大量的重复计算，比如用例中：6-2=4，6-1-1=4；导致4这个节点会被多次计算。
如图
值为4的节点和值为3的节点都多次出现。
参考代码如下：
class Solution {
private:
int _min_depth = INT_MAX; // 初始化递归深度为（近似）无限大
public:
void dfs(vector<int> &arr, int rem, int depth) {
if (rem == 0) {
_min_depth = min(_min_depth, depth); // 每次递归到结束条件就更新最小的深度
return ;
}
for (auto coin : arr)
dfs(arr, rem - coin, depth + 1); // 每次递归深度+1
}
int minMoney(vector<int>& arr, int aim) {
dfs(arr, aim, 0);
return _min_depth;
}
};
根据上文分析，可以将已经出现过的钱包剩余目标金额的最少硬币数记录下来，应该使用数组记录1 ~ aim范围内所有的金额的最少硬币数。
class Solution {
public:
int dfs(vector<int> &arr, vector<int> &mem, int aim) {
if (aim < 0) return -1;
if (aim == 0) return 0;
if (mem[aim] <= aim) return mem[aim];
for (int i = 0; i < arr.size(); ++i) {
int temp = dfs(arr, mem, aim-arr[i]);
if (temp != -1)
mem[aim] = min(mem[aim], temp + 1);
}
if (mem[aim] <= aim)
return mem[aim];
else
return mem[aim] = -1;
}
int minMoney(vector<int>& arr, int aim) {
vector<int> mem(aim + 1, aim + 1); // 初始化数组
return dfs(arr, mem, aim);
}
};
深度优先搜索采用自上而下的方法，“长”成了一棵树。
动态规划则是自下而上，找到每个节点的最小硬币数，不会是一个树状结构。
class Solution {
public:
int minMoney(vector<int>& arr, int aim) {
vector<int> dp(aim + 1, aim + 1);
dp[0] = 0;
for (int i = 1; i <= aim; ++i) {
for (int j : arr) {
if (i >= j)
dp[i] = min(dp[i], dp[i - j] + 1);
}
}
if (dp[aim] != aim + 1) return dp[aim];
else return -1;
}
};
有种错误的思路是，认为放尽量多的面额大的硬币就可以让使用硬币的数量最少（即贪心思想）。如果每种面额的硬币只有一枚，那么可以使用贪心思想。
然而，考虑这种情况：如目标金额10，硬币为7，5，1；则最少硬币数是2（5+5）而不是4（7+1+1+1）。
这里也提供错误思路的代码：
class Solution {
private:
int _min_depth = INT_MAX;
int flag = false;
public:
void dfs(vector<int>& arr, int rem, int depth) {
if (rem == 0) {
flag = true;
_min_depth = depth;
return ;
}
for (auto coin : arr) {
if (!flag) dfs(arr, rem - coin, depth + 1);
}
}
int minMoney(vector<int>& arr, int aim) {
sort(arr.begin(), arr.end(), greater<>());
dfs(arr, aim, 0);
return _min_depth == INT_MAX ? -1 : _min_depth;
}
};
我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou
我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中，我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-
我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t
我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为
为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar
我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',
我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby1.9+ 关于ruby-主要:Objectwhenrun
我花了三天的时间用头撞墙，试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上，从现在开始，您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳