利用递归解决问题的一些实例讲解

机器人运动范围

题目描述：
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题分析：
（1）利用递归求解，递归的结束条件：当前格子的坐标数位之和>设定的阈值，或者不在[0,rows-1] [0,cols-1]范围内，为了避免重复搜索，需要设置一个flag[curRow][curRow]用于记录当前格子被浏览过。
（2）check()函数的实现。用n%10取最低位，n/10取除最低位之外的整数；依次循环直到n=0为止，即可求出每一位

public class Solution { public int movingCount(int threshold, int rows, int cols){ int[][] flag=new int[rows][cols]; return movingCountHelper(threshold,rows,cols,0,0,flag); } private int movingCountHelper(int threshold,int rows,int cols,int curRow,int curCol,int[][] flag){ //特判，当前格子不在[0,rows]和[0,cols] if(curRow<0 || curRow>rows-1 || curCol<0 || curCol>cols-1 || flag[curRow][curCol]==1 || !check(curRow,curCol,threshold)){ return 0; } flag[curRow][curCol]=1;//设置当前格子已经走过； //递归查找，向左、右、上、下分别递归寻找。 return 1+movingCountHelper(threshold,rows,cols,curRow,curCol+1,flag) +movingCountHelper(threshold,rows,cols,curRow,curCol-1,flag) +movingCountHelper(threshold,rows,cols,curRow+1,curCol,flag) +movingCountHelper(threshold,rows,cols,curRow-1,curCol,flag); } //检查当前坐标 private boolean check(int row,int col,int threshold){ int res=0; while(row!=0){ res+=row%10;//取最低位； row=row/10;//取除去最低位的数； } while(col!=0){ res+=col%10; col=col/10; } if(res>threshold){ return false; } return true; } } 

从矩阵种匹配字符串

题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
题目分析
和上一题几乎是一模一样的思想，递归+回溯，递归的本质就是只负责自己的活，下一步的逻辑和当前逻辑一样（调用自己）
（1）递归函数的功能就是判断当前坐标位置的值和str中对应的值是否相同，如果相同，则可以选择上、下、左、右任意一个方向进行递归的匹配，递归体现在：str中的字符向下一位；
（2）需要设置一个变量visited[][]用于记录当前的格子是否被访问过。当前匹配成功，需要将其设置为1；
（2）如果当前格子中的字符和str[i]的字符匹配不成功，则需要回溯到原来的状态（visted[][]==flase）,设置当前的格子未被浏览，即是回溯的操作；

public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str){ if(rows*cols<str.length){ return false; } int[][] flag=new int[rows][cols]; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if( pathHelper(matrix,rows,cols,i,j,str,0,flag)){ return true; } } } return false; } private boolean pathHelper(char[] matrix,int rows,int cols,int curRow,int curCol,char[] str,int curChar,int[][] flag){ //将二维数组转化为一维数组 int index=curRow * cols+curCol; if(curRow<0 || curRow>=rows || curCol<0 || curCol>=cols || flag[curRow][curCol]==1 || matrix[index]!=str[curChar]){ return false; } //字符串全部匹配完成 if(curChar==str.length-1){ return true; } //否则，该路径可以 flag[curRow][curCol]=1;//记录这条路已经走了 if(pathHelper(matrix,rows,cols,curRow-1,curCol,str,curChar+1,flag) || pathHelper(matrix,rows,cols,curRow+1,curCol,str,curChar+1,flag) || pathHelper(matrix,rows,cols,curRow,curCol+1,str,curChar+1,flag) || pathHelper(matrix,rows,cols,curRow,curCol-1,str,curChar+1,flag) ){ return true; } //走到这一步，必然匹配失败，进行回溯 flag[curRow][curCol]=0;//回溯 return false; } } 

---

矩形覆盖问题

题目描述：
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法
解题思路：

public class Solution { public int RectCover(int target) { if (target < 1) { return 0; } else if (target == 1 || target == 2) { return target; } else { //target-1  表示上一个矩形 return RectCover(target-1) + RectCover(target-2); } } } 

---

跳阶梯问题I

问题描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题步骤：
暴力枚举：设dp[i]表示跳到第i阶的跳数，则dp[n]为所求解，
初始化条件：dp[0]=dp[1]=1;
核心思想，如果从上一级跳1步到第i级，则上一级为 i-1；
如果上一级跳2步到i，则上一级为i-2；

public class Solution { public int JumpFloorII(int target) { //dp[i],表示跳上i级台阶的跳法 //先计算跳上i级台阶的跳数，再计算从i级到target的跳数 int[] dp=new int[target+1]; dp[0]=1;//跳上1级台阶的跳法 dp[1]=1; for(int i=2;i<=target;i++){ //枚举跳上i的跳法 for(int j=0;j<i;j++){ dp[i]+=dp[j]; } } return dp[target]; } } 

---

跳阶梯问题II

题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路：
xian来分析问题:
设：dp[i]表示跳到i级台阶的总跳法，由于只能跳1步或者2步，那么从上一步只可能为：i-1或者i-2，即dp[i]=dp[i-1]+dp[i-2];
很显然，这是一个动态规划的问题：
base_case:dp[0]=1,dp[1]=1;

public class Solution { public int JumpFloor(int target) { int[] dp=new int[target+1]; dp[0]=1; dp[1]=1; for(int i=2;i<=target;i++){ dp[i]=dp[i-1]+dp[i-2]; } //dp[target]; return dp[target]; } } 

跳台阶问题III

问题描述：
给定一个非负整数数组，数组元素表示你在该位置能可以跳跃的最大长度，判断你是否能跳到最后的位置
例如：[2,3,1,1,4],可以从初始位置0先跳1步到达1位置，然后再跳3步及到达最后位置，故返回true
解题步骤：
可以使用贪心算法，这道题目可以换个思路：从位置i最远可以跳多远fast，如果这个fast>n-1，则必然可以跳到最后的位置

public class Solution { public int JumpFloor(int[] nums) { int fastest=0; for(int i=0;i<nums.length-1;i++){ fastest=Math.max(fastest,i+nums[i]); if(fastest<=i){ return false; } } //长度为n的数组，最多需要跳n-1步； return fastest>=n-1; } } 

跳台阶问题IIII

在上述“跳台阶问题III”的基础上，求最少的跳的步数到达最后一个位置
解题思路：
使用谈心算法，每一步跳到最大位置，然后再从这个位置又选择最大的位置进行跳跃

public class Solution { public int JumpFloor(int[] nums) { int fastest=0; int end=0//记录每一跳的结束位置 int jump=0; for(int i=0;i<nums.length-1;i++){ fastest=Math.max(fastest,i+nums); //跳到最远位子再计数 if(i==end){ jump++; end=fastest;//将当前fastest更新到全局， } } } } 

本文地址：https://blog.csdn.net/qq_31032005/article/details/107604822