一救援机器人有三种跳跃模式，可分别跳跃1m，2m，3m的距离，请用程序实现该机器人行进n米路程时可用的跳跃方式。
程序语言不限，当距离n值足够大时，程序执行时间尽量小。
例：当距离为4米时，输出结果有7种：
1m,1m,1m,1m1m,1m,2m1m,2m,1m1m,3m2m,1m,1m2m,2m3m,1m

回复内容： 一救援机器人有三种跳跃模式，可分别跳跃1m，2m，3m的距离，请用程序实现该机器人行进n米路程时可用的跳跃方式。
程序语言不限，当距离n值足够大时，程序执行时间尽量小。
例：当距离为4米时，输出结果有7种：
1m,1m,1m,1m1m,1m,2m1m,2m,1m1m,3m2m,1m,1m2m,2m3m,1m

谢谢邀请。
出这道题，明显是为了考察你 dp。我也不多说，直接放码过来了：
cppvoid step(int n, std::string str) { if (n == 0) { std::cout = 1) step(n-1, str+1m,); if (n >= 2) step(n-2, str+2m,); if (n >= 3) step(n-3, str+3m,);}
当 n == 4 的时候，调用：step(4, ); 原样输出你想要的。
这里只是用最短的代码表述我的思路，怕爆栈的，自行修改。
it is quite similar to my facebook interview question: a game has 3 levels of scores: 1 point, 2 points, 5 points. please print all the ways you can get 10 points.
简单想了一下，这道题目优化思路和斐波那契数列的优化思路相同:记录f(n)。
根据题目可知f(n)=f(n-1)+f(1)=f(n-2)+f(2)=f(n-3)+f(3)=f(1)+f(n-1)=..
手机码字后面两个等式就不写了。
f(n)的可能也就这6种(当然肯定包含重复)
那么一点点推导f(4)因为f123已知，f4可以在o(1)内得到，记录。
f5，此时f1234已知，f5也能在o(1)得到，记录。
那么f(n)，根据上述的公式，可以在o(n)内得到。
这是大致思路，接下来解决重复问题就行了。
根据 @auv_503516 的思路, 写以下代码, 存储结构和空间还可以优化
#!/usr/bin/env python3# -*- coding: utf-8 -*-## @file robot_steps_calculator.py # @author kaka_ace# @date mar 27 2015# @breif #import copyclass robotbrain(object): cache_init = { 1: [['1']], 2: [['1', '1'], ['2']], 3: [['1', '1' ,'1'], ['1', '2'], ['2', '1'], ['3']], } cache_key_map_init = dict() # 缓存如 '11', '21' etc. 去重作用 for k, v in cache_init.items(): for l in v: s = .join(l) cache_key_map_init[s] = true def __init__(self): self.cache = copy.deepcopy(self.cache_init) self.cache_key_map = copy.deepcopy(self.cache_key_map_init) def output_solution(self, n: total length, positive number) -> none: if n none: for sl in self.cache[i-delta]: s = ''.join(sl) delta_str = str(delta) if reverse is true: # delta + f(i - delta) new_key = delta_str + s else: # f(i - delta) + delta new_key = s + delta_str if new_key not in self.cache_key_map: self.cache_key_map[new_key] = true self.cache[i].append([delta_str] + sl) @staticmethod def _ouput_result(cache_list) -> none: for cache_result in cache_list: print(,.join([i+m for i in cache_result]))if __name__ == __main__: r = robotbrain() r.output_solution(5)
用c写了一段:
unsigned int count(unsigned int n){ switch(n) { case 0: return 0; case 1: return 1; case 2: return 2; case 3: return 4; default: return (count(n - 1) + count(n - 2) + count(n - 3)); } return 0;}
运行结果：
n = 0; t = 0n = 1; t = 1n = 2; t = 2n = 3; t = 4n = 4; t = 7n = 5; t = 13n = 6; t = 24n = 7; t = 44n = 8; t = 81n = 9; t = 149...
好吧，原来是要详细列出每种方法的方案，我没认真看…… =_,=b
直接采用递归的话会有很多重复的计算，比如在n=7的时候，会有1+1+1+steps(4)，1+2+steps(4)，3+steps(4)，所以step（4）会被重复计算多次。因此在需要做记忆之前的结果
int steps[length] = {0, 1, 2, 4};int n, i;for ( i = 4; i
写个for循环算了，
这也就oi初中组的水平......典型的动态规划一点儿弯儿都没绕
这也就是考递归的问题.
如果是要求一共有多少种方法，就可以简单用一位数组做动态规划。如果要求输出所有解，就老老实实的求吧。代码用递归写的。
java /** * return number of all distinct paths for a given distance.. * o(n) time and o(n) space using dp. */ public int allpath(int n) { int[] dp = new int[n+1]; dp[0] = 1; // useless dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i > allpaths(int n) { list> res = new arraylist>(); helper(n, 0, new arraylist(), res); return res; } private void helper(int n, int cur, list list, list> res) { if (cur > n) { return; } if (cur == n) { res.add(list); return; } for (int i = 1; i newlist = new arraylist(list); newlist.add(i); helper(n, cur + i, newlist, res); } }
分别n/3,n/2,看余数是多少。如果被3整除就是3333...; n/3有余数y2，y2/2没有余数，就是33333...2; n/3有余数y2，y2/2也有余数，最终的余数就用1来跳,3333...1。上面是n很大的情况。如果n小于等于3，一步就够。
f(n)=1,n=1
f(n)=2,n=2
f(n)=4,n=3
f(n)=f(n-1)+f(n-2)+f(n-3),n>3
int fuck(int length){ if(length
指数的时间复杂度，因为产生了重复计算，按照斐波那契数列的方法，改成迭代或者在递归函数里多传点参数，时间复杂度能变成线性的。
艹，看错题目了,将错就错
void p(const list &state){ for(auto it=state.begin();it!=state.end();it++) if(it != --state.end()) cout append(list m,int k){ m.push_back(k); return m;}int cfuck(int length,list state){ if(length
哎，c++知识全忘光了（反正我也进不了雅虎）。不过这道题目无论怎么样时间复杂度都是指数级的，所以就无所谓在最短的时间内了
大神你们都超屌的