递归和动态规划题目代码

递归

暴力递归： 1.把问题转化为规模缩小了的同类问题的子问题 2.有明确的不需要继续进行递归的条件(base case) 3.有当得到了子问题的结果之后的决策过程 4.不记录每一个子问题的解 1.求n!的结果

public class hello { public static long getFactorial1(int n) { if (n == 1) { return 1L; } return (long) n * getFactorial1(n - 1); } public static void main(String[] args) { int n = 5; System.out.println(getFactorial1(n)); } }

2.汉诺塔问题 打印n层汉诺塔从最左边移动到最右边的全部过程

public class hello { public static void hanoi(int n) { if (n > 0) { func(n, n, "left", "mid", "right"); } } //1，2，3号柱子从左到右依次排列，起始时依次是from,help，to public static void func(int rest, int down, String from, String help, String to) { if (rest == 1) { //只有一个盘子 System.out.println("move " + down + " from " + from + " to " + to); } else { //1，2，3号柱子从左到右依次排列，1号柱子的n-1盘子个放到2号 func(rest - 1, down - 1, from, to, help); //剩下的一个盘子从1号放到3号 func(1, down, from, help, to); //将2号的n-1个盘子放到3号 func(rest - 1, down - 1, help, from, to); } } public static void main(String[] args) { int n = 3; hanoi(n); } }

3.打印子序列 打印一个字符串的全部子序列，包括空字符串

public class hello { //打印字符串所有子序列 public static void printAllSubsquence(char[] str,int i,String res) { //当i达到字符串长度，输出结束返回，达到递归终止条件 if(i==str.length) { System.out.println(res); return; } printAllSubsquence(str,i+1,res);//不加该字符 printAllSubsquence(str,i+1,res+String.valueOf(str[i]));//加上该字符 } public static void main(String[] args) { String test = "abc"; char[] a=test.toCharArray(); printAllSubsquence(a,0,""); } }

4.母牛数量 母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只 母牛，假设不会死。求N年后，母牛的数量。 N>3时，F(N)=F(N-1)+F(N-3)

public class hello { public static int cowNumber1(int n) { if (n < 1) { return 0; } //前三年每年只有1头牛 if (n == 1 || n == 2 || n == 3) { return n; } //三年以后每年牛的数量都是前一年的牛加前三年的牛 return cowNumber1(n - 1) + cowNumber1(n - 3); } public static void main(String[] args) { int n = 20; System.out.println(cowNumber1(n)); } }

结果：1873 5.求整棵树的最大搜索二叉子树

package cao; public class hello { //定义树的节点 public static class Node{ public int value; public Node left; public Node right; public Node(int val) { this.value = val; } } //返回信息 public static class returnType{ public int size;//最大搜索子树节点的数量 public Node head;//最大搜索二叉树的头 public int min;//该树的最小值 public int max;//该树的最小值 public returnType(int a,Node b,int c,int d){ this.size=a; this.head=b; this.min=c; this.max=d; } } public static returnType process(Node head){ if(head==null){ return new returnType(0,null,Integer.MAX_VALUE,Integer.MIN_VALUE); } Node left = head.left; Node right = head.right; returnType leftsub=process(left);//左树生成的信息 returnType rightsub=process(right);//右数生成的信息 int includeSelf=0; //左树最大搜索二叉子树的头部是左孩子&&右树最大搜索二叉子树的头部是右孩子 if(leftsub.head==left&&rightsub.head==right && head.value>leftsub.max &&head.value<rightsub.min){ includeSelf=leftsub.size+1+rightsub.size; } int p1=leftsub.size; int p2=rightsub.size; int maxsize=Math.max(Math.max(p1,p2),includeSelf); Node maxhead = p1>p2?leftsub.head:rightsub.head; if(maxsize==includeSelf){ maxhead=head; } return new returnType(maxsize,maxhead,Math.min(Math.min(leftsub.min,rightsub.min),head.value),Math.max(Math.max(leftsub.max,rightsub.max),head.value)); } public static void main(String[] args) { Node head = new Node(7); head.left = new Node(3); head.right = new Node(10); head.left.left = new Node(2); head.left.right = new Node(4); head.right.left = new Node(8); head.right.right = new Node(11); System.out.println(process(head).size); } }

结果：7 6.二叉树上最远距离 从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。对于给定的一棵二叉树，求整棵树上节点间的最大距离。给定一个二叉树的头结点root，请返回最大距离。 分析：有三种可能性：（1）最大距离在左树（2）最大距离在右树（3）最大距离为左树深度->当前节点->右树深度

package cao; public class hello { //定义结点 public static class Node{ public int value; public Node left; public Node right; public Node(int val) { this.value = val; } } //返回类型 public static class returnType{ public int juli;//该点离其他点的最大距离 public int height;//该节点的深度 public returnType(int juli,int height){ this.juli=juli; this.height=height; } } //求最大距离 public static int maxDistance(Node head){ return process(head).juli; } public static returnType process(Node head){ if(head==null){ return new returnType(0,0); } Node left = head.left; Node right = head.right; returnType leftsub=process(left);//左树生成的信息 returnType rightsub=process(right);//右数生成的信息 int includeSelf=leftsub.height+1+rightsub.height;//可能性3：左边的最大高度加右边的最大高度+自身（1） int p1=leftsub.juli;//可能性1：左边最大距离 int p2=rightsub.juli;//可能性2：右边最大距离 int resultDistance=Math.max(Math.max(p1,p2),includeSelf);//可能性1，2，3产生的最大的距离 int heightself=Math.max(leftsub.height,rightsub.height)+1;//左边和右边的深度大的+1 return new returnType(resultDistance,heightself); } public static void main(String[] args) { Node head = new Node(7); head.left = new Node(3); head.right = new Node(10); head.left.left = new Node(2); head.left.right = new Node(4); head.right.left = new Node(8); head.right.right = new Node(11); System.out.println(maxDistance(head));//结果：5 } }

7.公司员工参加晚会问题 一个公司的上下节关系是一棵多叉树，这个公司要举办晚会，你作为组织者已经摸清了大家的心理：一个员工的直接上级如果到场，这个员工肯定不会来。每个员工都有一个活跃度的值，决定谁来你会给这个员工发邀请函，怎么让舞会的气氛最活跃？返回最大的活跃值。

package cao; import java.util.ArrayList; import java.util.List; public class hello { //定义结点 public static class Node{ public int huo;//活跃度 public List<Node> nexts;//下一级节点 public Node(int huo) { this.huo = huo; nexts = new ArrayList<>(); } } //返回类型 public static class returnType{ public int lai_huo;//该点参加活动的活跃度 public int bulai_huo;//该节点不参加活动的活跃度 public returnType(int lai_huo,int bulai_huo){ this.lai_huo=lai_huo; this.bulai_huo=bulai_huo; } } //求最大活跃度 public static int maxhuo(Node head){ returnType data=process(head); return Math.max(data.bulai_huo,data.lai_huo); } public static returnType process(Node head){ int lai_huo = head.huo; int bulai_huo = 0; for(int i=0;i<head.nexts.size();i++){ Node next = head.nexts.get(i); returnType nexttype=process(next); lai_huo+=nexttype.bulai_huo; bulai_huo+=Math.max(nexttype.bulai_huo,nexttype.lai_huo);//该节点不来时，下级节点可来可不来 } return new returnType(lai_huo,bulai_huo); } }

8.判断一棵树是否为平衡二叉树

package cao; import sun.reflect.generics.tree.ReturnType; import java.util.ArrayList; import java.util.List; public class hello { //定义结点 public static class Node{ public int value;//活跃度 public Node left; public Node right; public Node(int data) { this.value = data; } } //返回类型 public static class returnType{ public int h; public boolean isB; public returnType(int h,boolean isB){ this.h=h; this.isB=isB; } } //求最大活跃度 public static boolean isB(Node head){ return process(head).isB; } public static returnType process(Node head){ if(head==null){ return new returnType(0,true); } returnType leftdata=process(head.left); if(!leftdata.isB){ return new returnType(0,false); } returnType rightdata=process(head.right); if(!rightdata.isB){ return new returnType(0,false); } if(Math.abs(leftdata.h-rightdata.h)>1){ return new returnType(0,false); } return new returnType(Math.max(leftdata.h,rightdata.h)+1,true); } public static void main(String[] args){ Node head = new Node(5); head.left = new Node(3); head.right = new Node(8); head.left.left = new Node(2); head.left.right = new Node(4); head.right.left = new Node(7); head.right.right = new Node(10); System.out.println(isB(head)); } }

总结： （1）列出所有可能性 （2）返回值结构类型 （3）basecase考虑

动态规划

动态规划 1.从暴力递归中来 2.将每一个子问题的解记录下来，避免重复计算 3.把暴力递归的过程，抽象成了状态表达 4.并且存在化简状态表达，使其更加简洁的可能 1.最小路径和 给你一个二维数组，二维数组中的每个数都是正数，要求从左上 角走到右下角，每一步只能向右或者向下。沿途经过的数字要累 加起来。返回最小的路径和。 思路：确定起终点位置-不被依赖位置的确定-逆推

public class hello { public static int minPath1(int[][] matrix) { //从左上角到右下角会有重复节点计算例如（0，1）跟（1，0）都要计算（1，1），因此从右下角计算 //从右下角计算推至左下角 return process1(matrix, matrix.length - 1, matrix[0].length - 1); } public static int process1(int[][] matrix, int i, int j) { int res = matrix[i][j]; //点已经到达左上角，直接返回 if (i == 0 && j == 0) { return res; } //点一直在第一行 if (i == 0 && j != 0) { return res + process1(matrix, i, j - 1); } //点一直在第一列 if (i != 0 && j == 0) { return res + process1(matrix, i - 1, j); } //返回当前节点的值加左或上已经算好的最小值 return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j)); } public static void main(String[] args) { int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } }; System.out.println(minPath1(m)); } }

结果：12 2.累加值 给你一个数组arr，和一个整数aim。如果可以任意选择arr中的 数字，能不能累加得到aim，返回true或者false

public class hello { //从0位置开始，和起始为0 public static boolean money1(int[] arr, int aim) { return process1(arr, 0, 0, aim); } //计算是否能得到累加和 public static boolean process1(int[] arr, int i, int sum, int aim) { //和等于目标值，返回true if (sum == aim) { return true; } // sum != aim if (i == arr.length) { return false; } //返回和加当前数值或不加当前数值的或 return process1(arr, i + 1, sum, aim) || process1(arr, i + 1, sum + arr[i], aim); } public static void main(String[] args) { int[] arr = { 1, 4, 8 }; int aim = 12; System.out.println(money1(arr, aim)); } }