【每日一题 6.26】不同路径

开始之前先给自己打个鸡血吧：
A journey of a thousand miles begins with a single step. 千里之行始于足下。

题源：https://leetcode.cn/problems/unique-paths/
题目详情：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径。

思路
这一题同样用了【动态规划】的思想
此种方法c语言代码内存开销较大，目前还未想到优化方法
代码

python

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        road = [[1]*n] + [[1]+[0] * (n-1) for i in range(m-1)]
        for i in range(1, m):
            for j in range(1, n):
                road[i][j] = road[i-1][j] + road[i][j-1]
        return road[-1][-1]

c语言

int uniquePaths(int m, int n){
    //road[i][j]代表从左上角走到此位置的路径数量
    int road[100][100]={0};
    int i,j=0;
    //边界上只有一种走法
    for(i=0;i
        road[0][i]=1;
    }
    for(j=1;j
        road[j][0]=1;
    }
    for(i=1;i
        for(j=1;j
            //当前位置走法数为上和左位置的和
            road[i][j]+=road[i-1][j]+road[i][j-1];
        }
    }
    return road[m-1][n-1];
}