赞
踩
1.台阶问题
有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。为了防止溢出,请将结果Mod 1000000007
给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100000。
思路:动态规划问题也可以说是斐波那契数列。如果只有一个台阶f[1]=1,有两个台阶f[2]=2.
- public class GoUpstairs {
- public int countWays(int n) {
- // write code here
- int[] f=new int[n+1];
- f[0]=1;//0级台阶
- f[1]=1;
- f[2]=2;
- for(int i=3;i<=n;i++){
- f[i]=(f[i-1]+f[i-2])%1000000007;
- }
- return f[n];
- }
- }
2.矩阵最小路径问题
有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。
给定一个矩阵map及它的行数n和列数m,请返回最小路径和。保证行列数均小于等于100
思路: 首先创建和map等大小的二维数组dp
dp[i][j]=来到节点(i,j)的步数,要么是从(i-1,j)向下走的,要么是(i,j-1)向右走的
- public class MinimumPath {
- public int getMin(int[][] map, int n, int m) {
- // write code here
- int[][] dp=new int[n][m];
- dp[0][0]=map[0][0];
- for(int i=1;i<m;i++) dp[0][i]=dp[0][i-1]+map[0][i];//第一行
- for(int i=1;i<n;i++) dp[i][0]=dp[i-1][0]+map[i][0];//第一列
-
- //dp[i][j]=来到节点(i,j)的步数,要么是从(i-1,j)向下走的,要么是(i,j-1)向右走的
- for(int i=1;i<n;i++){
- for(int j=1;j<m;j++){
- dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+map[i][j];
- }
- }
- return dp[n-1][m-1];
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。