电子商务网站推广策略主要内容,磁力搜索引擎,抚州招聘网站建设,wordpress获取缩略图地址题目一#xff1a;不同路径的数目#xff08;一#xff09;
题目描述#xff1a;
一个机器人在mn大小的地图的左上角#xff08;起点#xff09;。机器人每次可以向下或向右移动。机器人要到达地图的右下角#xff08;终点#xff09;。可以有多少种不同的路径从起点…题目一不同路径的数目一
题目描述
一个机器人在m×n大小的地图的左上角起点。机器人每次可以向下或向右移动。机器人要到达地图的右下角终点。可以有多少种不同的路径从起点走到终点 输入输出描述
输入2,2 返回值2
题目解析 step 1用dp[i][j]表示大小为i∗j的矩阵的路径数量下标从0开始。step 2初始条件 当i或者j为0的时候代表矩阵只有一行或者一列因此只有一种路径。step 3转移方程 每个格子的路径数只会来自它左边的格子数和上边的格子数因此状态转移为dp[i][j]dp[i−1][j]dp[i][j−1]。
作答情况
属于简单题正确。
代码
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param m int整型 * param n int整型 * return int整型*/public int uniquePaths (int m, int n) {int[][] dpnew int[m][n];for(int i0;im;i){for(int j0;jn;j){if(i0||j0) {dp[i][j]1;}else{dp[i][j]dp[i][j-1]dp[i-1][j];}}}return dp[m-1][n-1];}
}
题目二短距离最小路径和
题目描述
给定一个 n * m 的矩阵 a从左上角开始每次只能向右或者向下走最后到达右下角的位置路径上所有的数字累加起来就是路径和输出所有的路径中最小的路径和。
输入输出描述
输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]] 返回值12
说明 题目解析 step 1我们可以构造一个与矩阵同样大小的二维辅助数组其中dp[i][j]表示以(i,j)位置为终点的最短路径和。step2判断特殊情况二维数组只有一个值时dp[0][0]matrix[0][0]。step 3很容易知道第一行与第一列只能分别向右或向下没有第二种选择因此第一行只能由其左边的累加第一列只能由其上面的累加。step4只有一行或一列时只能向右或向下走过来(一行) dp[0][j]matrix[0][j]dp[0][j-1]; 一列 dp[i][0]matrix[i][0]dp[i-1][0];step 5边缘状态构造好以后遍历矩阵补全矩阵中每个位置的dp数组值因此状态转移公式为dp[i][j]min(dp[i−1][j],dp[i][j−1])matrix[i][j]。step 4最后移动到(n−1,m−1)的位置就是到右下角的最短路径和。
作答情况
没有判断一行或一列情况下的特殊情况。
代码
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param matrix int整型二维数组 the matrix* return int整型*/public int minPathSum (int[][] matrix) {int mmatrix.length;int nmatrix[0].length;int[][] dpnew int[m][n];for(int i0;im;i){for(int j0;jn;j){//终点即起点if(i0j0) dp[i][j] matrix[i][j];//只有一行else if(i0) dp[i][j]matrix[i][j]dp[i][j-1];//只有一列else if(j0) dp[i][j]matrix[i][j]dp[i-1][j];//多行多列下任意位置前一个只能向下或向右来到达else dp[i][j]Math.min(dp[i-1][j],dp[i][j-1])matrix[i][j];}}//移动到右下角return dp[m-1][n-1];}
}
题目三把数字翻译成字符串
题目描述
有一种将字母编码成数字的方式a-1, b-2, ... , z-26。现在给一串数字返回有多少种可能的译码结果。
输入输出描述
输入12 返回值2
说明2种可能的译码结果”ab” 或”l”
输入31717126241541717 返回值192
题目解析
1.用辅助数组dp表示前i个数的译码方法有多少种。
2.数字为单数数字非零1种数字为零0种
3.数字为多位数
3.1 数字种存在0数字中有10和20两位数1种多位数dp[i]dp[i-2]种 数字不是10和200种
3.2 数字中没有0数字范围为11~19 21~26 两位数2种多位数dp[i]dp[i-2]dp[i-1]种 数字范围大于26两位数和多位数都是dp[i]dp[i-1]
作答情况
数字种存在0数字中有10和20 没有判断两位数和多位数情况。
代码
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 解码* param nums string字符串 数字串* return int整型*/public int solve (String nums) {int mnums.length();//dp[i]到了i位置上把数字翻译成字符串的方式有几种int[] dpnew int[m];//(数字是单数)if(nums.charAt(0)!0) dp[0]1;else dp[0]0;//数字是多位数从第二位开始遍历for(int i1;idp.length;i){//尾位置存在0if(nums.charAt(i)0){//0前面是1或2开头
if(nums.charAt(i-1)1||nums.charAt(i-1)2){//数字是两位if(i1) dp[i]1; //数字是多位else dp[i]dp[i-2];
}
// //0前面不是1或2开头
else{dp[i]0;
}}//尾位置不存在0else {
if((nums.charAt(i-1)1nums.charAt(i)9)||(nums.charAt(i-1)2nums.charAt(i)6)){//两位if(i1) dp[i]2;// 多位else
dp[i]dp[i-1]dp[i-2];
}
else dp[i]dp[i-1];}}return dp[m-1];}
}
