赞
踩
动态规划,相信对于一些刚学习算法的朋友来说,动态规划是算法在最难以理解,和自己设计时都苦恼。现在,我就以这题来给大家伙们讲。
讲之前,我们要知道动规是一个什么玩意
动规其实和分治法很相似,其基本思想都是将问题分解成若干个子问题,进而求解子问题在得到原问题的解。与分治法不同的是,动规分解后的子问题并不是互相独立的,这样做的避免出现分治法的子问题重叠,从而提高效率。
这题是指一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
由于题目指明,只能往右移动和往下移动,所以每移动一次,都要再进行向右或者向下的选择,可以分解成相同的子问题,再依次相加。
而我的想法是先将一直往右走,走到头在往下走到终点,和一直往下走,在往右走的俩种方式先进行。接着就是其他情况,想走到某一块格子,上一步必须是这块格子的左边或者上边的格子
所以dp[i][j]==dp[i][j-1]+dp[i-1][j];
接着我们要想清楚,最后retur的结果要是什么?这个就要知道数组下标是从0开始的,而finish则在(2,6)这个格子,所以最后retur dp[i-1][j-1]
以下是代码
- package day06;
-
- import java.util.Scanner;
-
- public class DongGui1 {
- public static void main(String[] args) {
- int i,j;
- Scanner sc = new Scanner(System.in);
- i=sc.nextInt();
- j=sc.nextInt();
- int l=dg1(i,j);
- System.out.println(l);
- }
- public static int dg1(int m,int n){
- if (m<=0||n<=0){
- return 0;
- }
- int[][] dp = new int[m][n];
- for (int i = 0; i < m; i++) {
- dp[i][0]=1;
- }
- for (int i = 0; i < n; i++) {
- dp[0][i]=1;
- }
- for (int i = 1; i < m; i++) {//向下走
- for (int j = 1; j < n; j++) {//向右走
- dp[i][j]=dp[i-1][j]+dp[i][j-1];//依次相加
- }
- }
- return dp[m-1][n-1];
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。