寒光博客

[CC150]902机器人走方格问题
题目描述 有一个X*Y的网格,一个机器人只能走格点且只能向下或向右走,要从左上角走到右下角。 请设计一个算法,计算...
扫描右侧二维码阅读全文
30
2019/07

[CC150]902机器人走方格问题

题目描述

有一个X*Y的网格,一个机器人只能走格点且只能向下或向右走,要从左上角走到右下角。 请设计一个算法,计算机器人有多少种走法。 给定两个正整数int x,int y,请返回机器人的走法数目,保证x+y小于等于12。

分析

先假如只有1个格子,那很明显只有一种走法,那么我们再去画 12,21,13,31,也只有1种走法,再去画22 的方格,发现有两种走法了。
当2
2的时候发现他是由12 和21构成.....
所以

我们根据分析就可以得出这个递推式f(x,y)=f(x-1,y)+f(x,y-1)(因为只能向右走和向下走)

  所以我们可以使用递归的方式来解决这个问题,其次我们也可以使用迭代(递推)的方式来解决,因为涉及到两个变量都在变化,使用一维的变量是不能够保存的,所以要使用二维的数据结构:二维数组来保存从起始点到某一点的走法,比如说a[2][3]=3,表示机器人到这一个点总共有3种走法。

  使用递归的话就相当于一种富人的思想,把什么都交给手下人去做,自己只负责合并结果,代码很简洁。而迭代(递推)相当于打工者的思想,一步步根据自己的分析得出想要的结果,代码相对来说比递归要复杂一点。

代码

package BlueCup.Seven_recursion;

import java.util.Scanner;

public class _703_机器人走方格 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int x = cin.nextInt();
        int y = cin.nextInt();
        int ans = f(x, y);
        System.out.println(ans);
    }

    private static int solve(int x, int y) {
        //顺着想 倒着写
        if (x == 1) return 1;
        if (y == 1) return 1;
        return solve(x - 1, y) + solve(x, y - 1);
    }

    /**
     * 迭代形式
     */
    //dp公式 f(x,y)=f(x-1,y)+f(x,y-1);
    //当x或y=1时 无论怎样都只有一部
    public static int f(int m, int n) {
        int[][] state = new int[m + 1][n + 1];//缓存 想染色
        for (int i = 1; i <= n; i++) {//每一列的第一行
            state[1][i] = 1;
        }
        for (int i = 1; i <= m; i++) {//每一行的第一列
            state[i][1] = 1;
        }
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                state[i][j] = state[i][j - 1] + state[i - 1][j];
            }
        }
        return state[m][n];
    }
}
本文作者:Author:     文章标题:[CC150]902机器人走方格问题
本文地址:https://dxoca.cn/Algorithm/205.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 8th, 2019 at 01:33 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

4 comments

  1. Dxoca

    链接:https://www.nowcoder.com/questionTerminal/e8bb8e68434e42acbcdff0341f2a32c5
    来源:牛客网

    考虑原始DP问题为二维数组表示当前位置的步数,显然有: dp[i][j] = dp[i-1][j] + dp[i][j-1],而容易发现dp数组可以压缩为1维存储空间dp[y]。原dp[i-1][j]为上一行当前列的步数,而现dp[j]就存储了上一次该列的步数,而现dp[j-1]为左节点的步数即原dp[i][j-1]。
    所以变为:dp[j] = dp[j] + dp[j-1].

    class Robot {
    public:
        int countWays(int x, int y) {
            // write code here
            int dp[y];
            for(int i = 0; i < y; i++)
                dp[i] = 1;
            for(int i = 1; i < x; i++){
                for(int j = 1; j< y; j++){
                    dp[j] = dp[j] + dp[j-1];
                }
            }
            return dp[y-1];
        }
    };
  2. 10月就要奥赛了,加油!
    先顶过9月的物理再说

    1. Dxoca
      @灵

      加油 加油!!

      1. @Dxoca

        恩。一起努力