发布于 1970-01-01 08:00
  • 14 个回答
    • 谢谢邀请。

      出这道题,明显是为了考察你 DP。我也不多说,直接放码过来了:

      cppvoid step(int n, std::string str) {
          if (n == 0) { std::cout << str << "\b " << std::endl; }
          if (n >= 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, ""); 原样输出你想要的。


      这里只是用最短的代码表述我的思路,怕爆栈的,自行修改。

      2022-12-01 14:00 回答
    • 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.

      2022-12-01 14:00 回答
    • 简单想了一下,这道题目优化思路和斐波那契数列的优化思路相同:记录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)内得到。

      这是大致思路,接下来解决重复问题就行了。

      2022-12-01 14:00 回答
    • 根据 @AUV_503516 的思路, 写以下代码, 存储结构和空间还可以优化

      #!/usr/bin/env python3
      # -*- coding: utf-8 -*-
      #
      # @file     robot_steps_calculator.py 
      # @author   kaka_ace
      # @date     Mar 27 2015
      # @breif     
      #
      
      import copy
      
      class 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 <= 3:
                  print(RobotBrain._ouput_result(self.cache[n]))
                  return
      
              i = 4
              while i <= n:
                  """
                  f(i) = 1 + f(i-1)
                       = 2 + f(i-2)
                       = 3 + f(i-3)
      
                       = f(i-1) + 1
                       = f(i-2) + 2
                       = f(i-3) + 3
      
                      we need to remove duplicates
                  """
                  self.cache[i] = []
                  for step in range(1, 4):
                      self._add_to_cache(1, i, True)
                      self._add_to_cache(2, i, True)
                      self._add_to_cache(3, i, True)
      
                      self._add_to_cache(1, i, False)
                      self._add_to_cache(2, i, False)
                      self._add_to_cache(3, i, False)
      
                  i += 1
      
              self._ouput_result(self.cache[n])
      
          def _add_to_cache(self, delta: int, i: int, reverse: bool) -> 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)
      
      
      2022-12-01 14:00 回答
    • 用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 = 0
      n = 1; t = 1
      n = 2; t = 2
      n = 3; t = 4
      n = 4; t = 7
      n = 5; t = 13
      n = 6; t = 24
      n = 7; t = 44
      n = 8; t = 81
      n = 9; t = 149
      ...
      

      好吧,原来是要详细列出每种方法的方案,我没认真看…… =_,=b

      2022-12-01 14:00 回答
    • 直接采用递归的话会有很多重复的计算,比如在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 <= n; i++) {
              steps[i] = steps[i-1]+steps[i-2]+steps[i-3];
      }
      printf("%d\n", steps[n]);
      
      2022-12-01 14:00 回答
    • 写个For循环算了,

      2022-12-01 14:00 回答
    • 这也就OI初中组的水平......典型的动态规划一点儿弯儿都没绕

      2022-12-01 14:00 回答
    • 这也就是考递归的问题.

      2022-12-01 14:00 回答
    • 如果是要求一共有多少种方法,就可以简单用一位数组做动态规划。如果要求输出所有解,就老老实实的求吧。代码用递归写的。

      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 <= n; i++) {
                  dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
              }
              return dp[n];
          }
      
          /**
           *
           * return all distinct paths for a given distance.
           *
           */
          public List<List<Integer>> allPaths(int n) {
              List<List<Integer>> res = new ArrayList<List<Integer>>();
              helper(n, 0, new ArrayList<Integer>(), res);
              return res;
          }
          private void helper(int n, int cur, List<Integer> list, List<List<Integer>> res) {
              if (cur > n) {
                  return;
              }
              if (cur == n) {
                  res.add(list);
                  return;
              }
              for (int i = 1; i < 4 && cur + i <= n; i++) {
                  List<Integer> newList = new ArrayList<Integer>(list);
                  newList.add(i);
                  helper(n, cur + i, newList, res);
              }
          }
      
      2022-12-01 14:00 回答
    • 分别n/3,n/2,看余数是多少。如果被3整除就是3333...; n/3有余数y2,y2/2没有余数,就是33333...2; n/3有余数y2,y2/2也有余数,最终的余数就用1来跳,3333...1。上面是n很大的情况。如果n小于等于3,一步就够。

      2022-12-01 14:00 回答
    • 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

      2022-12-01 14:00 回答
    • int fuck(int length)
      {
          if(length <0)
          {
              return 0;
          }
          if(length == 1 || length == 0)
              return 1;
          return fuck(length-1)+fuck(length-2)+fuck(length-3);
      }
      

      指数的时间复杂度,因为产生了重复计算,按照斐波那契数列的方法,改成迭代或者在递归函数里多传点参数,时间复杂度能变成线性的。

      艹,看错题目了,将错就错

      void p(const list<int> &state)
      {
          for(auto it=state.begin();it!=state.end();it++)
              if(it != --state.end())
                  cout<<*it<<"m,";
              else
                  cout<<*it<<'m';
          cout<<endl;
      }
      
      list<int> append(list<int> m,int k)
      {
          m.push_back(k);
          return m;
      }
      
      int cfuck(int length,list<int> state)
      {
          if(length < 0){
              return 0;
          }
      
          if(length == 0) {
              p(state);
              return 1;
          }
      
          return cfuck(length-1,append(state,1))+cfuck(length-2,append(state,2))+cfuck(length-3,append(state,3));
      }
      

      哎,C++知识全忘光了(反正我也进不了雅虎)。不过这道题目无论怎么样时间复杂度都是指数级的,所以就无所谓在最短的时间内了

      2022-12-01 14:00 回答
    • 大神你们都超屌的

      2022-12-01 14:00 回答
    撰写答案
    今天,你开发时遇到什么问题呢?
    立即提问
    PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
    Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有