前言：如果题目做了不会或通过率低就那么过了，感觉还是有点遗憾，记录又不费时，日后闲暇时思索也是一种乐趣。
题目描述： 牛牛回家要走恰好n个台阶， 由于牛牛步伐不大，故单步最多只能跨越最多m个台阶，最少跨一个台阶。 牛牛有一个奇怪的习惯，他要求每步和之前两步走的台阶数目不能相同。 牛牛想知道有多少种不同的走法，答案对10的9次方+7取模。 输入描述： 一行输入两个整数n、m，表示台阶数目，单步跨越的最多台阶数目。 对于30％的数据有m<=n<=5。 对于60%的数据有n<=300。 对于100%的数据有1<=n<=100000，2<=m<=7。 输出描述： 一行一个整数，表示答案。 示例： 输入：7 3 输出：2 说明：仅[1,2,3,1],[1,3,2,1]两种
注：下面是代码。思路是dfs加剪支或预剪枝，但都存在递归太深导致栈溢出的问题，如n过万，递归都不行。
百度笔试：回家有n个台阶，每次至少走一个，但是要求每步和之前两步走的台阶数目不能一样
import java.util.*; public class Main { public static long total; final static int mod = 1000000007; // 太过累赘 public static void climb(int step, int left, String cur) { // 剪枝 if ((left < 0)) // 保证恰好走完台阶 return; int len = cur.length(); // 后续方法不需要这么麻烦剪枝 if (len >= 2) { if (cur.charAt(len - 1) == cur.charAt(len - 2)) // 保证最后一级台阶与前一台阶不同 return; if (len >= 3 && cur.charAt(len - 1) == cur.charAt(len - 3)) // 保证最后一级台阶与前两次跨越不同 return; } if (left == 0) { total = (total + 1) % mod; //System.out.println(cur); return; } for (int i = 1; i <= step; i++) { climb(step, left - i, cur + i); } } // 保存了前两步结点的递归 public static int res = 0; public static void dfs(int index, int n, int m, int last, int lastlast) { if (index == n) { res++; res = res % mod; return; } if (index > n) return; for (int i = 1; i <= m; i++) { if (i != lastlast && i != last) { dfs(index + i, n, m, i, last);//在里面进行修改，这一步的值在下一步就是last，last在下一步就是lastlast } } } // 带有备忘录的递归 public static Map<String, Integer> map = new HashMap<String, Integer>(); public static int dfsWithMemory(int index, int n, int m, int last, int lastlast) { if (index == n) { return 1; } if (index > n) return 0; String str = index + "," + last + "," + lastlast; if (map.containsKey(str)) return map.get(str); int lastRes = 0; for (int i = 1; i <= m; i++) { if (i != lastlast && i != last) { lastRes += dfsWithMemory(index + i, n, m, i, last);//在里面进行修改，这一步的值在下一步就是last，last在下一步就是lastlast } } lastRes = lastRes % mod; map.put(str, lastRes); return lastRes; } // 只提供一个思路，台阶数太多效果很差 public static int bfs(int n, int m) { int total = 0; Deque<String> queue = new ArrayDeque<>(); int index = 0, pre = 0, prepre = 0; String str = index + " " + pre + " " + prepre; queue.push(str); while(!queue.isEmpty()){ String pop = queue.pollFirst(); String[] s = pop.split(" "); index = Integer.parseInt(s[0]); pre = Integer.parseInt(s[1]); prepre = Integer.parseInt(s[2]); for(int i = 1; i <= m && (index + i) <= n; i++){ if(i != prepre && i != pre){ if(index + i < n){ int nextIndex = index + i; int nextPrepre = pre; int nextPre = i; str = "" + nextIndex + " "+ nextPre + " " + nextPrepre; queue.addLast(str); System.out.println("台阶数： "+ index +" 这次：" + i+ " 上一次台阶：" + pre + " 上两次台阶：" + prepre); }else{ System.out.println("台阶数： "+ n +" 这次：" + i+ " 上一次台阶：" + pre + " 上两次次台阶：" + prepre); total++; total = total % mod; } } } } return total; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); // 输入的总台阶数 int m = sc.nextInt(); // 单次最大跨越台阶数，单次最小跨越1个台阶 climb(m, n, ""); System.out.println(total); System.out.println("*********************"); dfs(0, n, m, 0, 0); System.out.println(res); System.out.println("*********************"); int i = dfsWithMemory(0, n, m, 0, 0); System.out.println(i); } } }题目： 给出被除数和除数，求出循环小数的开始位置（小数点之后的位数）和循环长度
输入描述： 第一行包含两个数字分别是被除数a和除数b （1<= a, b <= 1000000）
输出描述： 输出一行，包含一个两个数字，分别表示循环小数的开始位置和循环体的长度（无循环则开始位置为结束位置，长度为0）
输入 1 3 输出 0 1 输入 5 4 输出 2 0 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int a = sc.nextInt(); int b = sc.nextInt(); ArrayList<Integer> list = new ArrayList<>(); int tmp = a % b; // 这里面没有考虑无限不循环小数(可能整除相除得不到)，要么多次后整除，要么存在循环体 list.add(tmp); boolean ok = false; while (tmp > 0){ tmp = tmp * 10 % b; for(int i = 0; i < list.size(); i++){ if(list.get(i) == tmp){ // 若列表中已经出现相同余数，则说明出现循环体，循环体长度可以从出现循环位置得到 ok = true; System.out.println(i + " "+ (list.size()-i)); break; } } if (ok) break; list.add(tmp); } if(tmp == 0 && !ok) System.out.println((list.size()-1) + " "+ 0); } } }