LintCode 不同的路径题目分析代码

题目

有一个机器人的位于一个M×N个网格左上角(下图中标记为'Start')。 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角(下图中标记为'Finish')。 问有多少条不同的路径?

** 注意事项 n和m均不超过100 **

样例

diffRoute.PNG

以上3 x 7的网格中,有多少条不同的路径?

分析

典型的动态规划问题 容易分析出状态转移方程: dp[i][j] = dp[i-1][j] + dp[i][j-1]; 初始条件,就是第一列和第一行,因为只能向下或向右走,所以,第一列和第一行的值都为1.

代码

public class Solution {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here 
        int[][] dp = new int[m][n];
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for(int i = 0; i < m; i++) {
            dp[i][0] = 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];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

让 TensorFlow 估算器的推断提速百倍,我是怎么做到的?

TensorFlow 估算器提供了一套中阶 API 用于编写、训练与使用机器学习模型,尤其是深度学习模型。在这篇博文中,我们描述了如何通过使用异步执行来避免每次...

1542
来自专栏新智元

【深度学习Github 10万+源代码分析】Python是第三受欢迎语言

【新智元导读】编程语言是软件开发的主要工具。自20世纪40年代以来,已经有数百种语言被发明出来,每天大量的各种语言编写的代码活跃着代码库。本文作者从 GitHu...

3748
来自专栏ATYUN订阅号

使用OpenCV,Python和深度学习进行人脸识别

在这篇文章中,你将学会如何使用OpenCV、Python和深度学习在图像和视频流中执行人脸识别。我们今天将在这里使用的基于深度学习的面部嵌入,既高度准确又能够实...

3.3K5
来自专栏iOSDevLog

seaborn的介绍

Seaborn是一个用Python制作统计图形的库。它建立在matplotlib之上,并与pandas数据结构紧密集成。

3721
来自专栏磐创AI技术团队的专栏

Tensorflow 免费中文视频教程,开源代码,免费书籍.

Free-Tensorflow Tensorflow 免费中文视频教程,开源代码,免费书籍. ? 官方教程 官方介绍 https://tensorflow.go...

3996
来自专栏SDNLAB

SDN应用路由算法实现工具之Networkx

SDN(Software Defined Networking)是一种新型的网络架构,通过集中式的控制平面管理数据层面的转发等操作。网络的连通性是最基础的需求,...

3649
来自专栏python开发者

基于Python使用SVM识别简单的字符验证码的完整代码开源分享

关键字:Python,SVM,字符验证码,机器学习,验证码识别 1   概述 基于Python使用SVM识别简单的验证字符串的完整代码开源分享。 因为目前有了更...

42810
来自专栏量子位

TensorFlow新功能「AutoGraph」:将Python转换为计算图

昨天,TensorFlow推出了一个新功能「AutoGraph」,可以将Python代码(包括控制流print()和其他Python原生特性)转换为Tensor...

1253
来自专栏Hadoop数据仓库

HAWQ取代传统数仓实践(七)——维度表技术之维度子集

        有些需求不需要最细节的数据。例如更想要某个月的销售汇总,而不是某天的数据。再比如相对于全部的销售数据,可能对某些特定状态的数据更感兴趣等。此时事...

2375
来自专栏H2Cloud

A星路径搜索

摘要:   在人工智能中有一类问题是有确定解的,如路径、五子棋等,这样的问题非常适合使用搜索来解决。 路径搜索是一个很有趣的问题,在人工智能中算是很基础的问题。...

5294

扫码关注云+社区

领取腾讯云代金券