Unique Paths

问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了

class Solution {
public:
    int num[110][110];
    int dfs(int m,int n,int x,int y)
    {
        if(num[x][y]) return num[x][y];
        if(x==m-1 && y==n-1) return 1;
        if(x+1<m) num[x][y]+=dfs(m,n,x+1,y);
        if(y+1<n) num[x][y]+=dfs(m,n,x,y+1);
        return num[x][y];
    }
    int uniquePaths(int m, int n) {
        memset(num,0,sizeof(num));
        return dfs(m,n,0,0);
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hust Dating With Girls

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

    用户1624346
  • Spiral Matrix II

    问题:蛇形矩阵 分析:设置变量dir,0123分别代表方向右下左上 class Solution { public: int num[300][300]...

    用户1624346
  • Search a 2D Matrix

    问题:二维数组中是否存在一个数 class Solution { public: bool dfs(vector<vector<int> > &matr...

    用户1624346
  • LWC 61:738. Monotone Increasing Digits

    LWC 61:738. Monotone Increasing Digits 传送门:738. Monotone Increasing Digits Probl...

    用户1147447
  • hdu 5249 KPI 权值线段树裸题

    用户2965768
  • hust Dating With Girls

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

    用户1624346
  • 1021 个位数统计 (15 分)

    给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现...

    可爱见见
  • leetcode-367-Valid Perfect Square

    chenjx85
  • 【LeetCode】221. 最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    韩旭051
  • leetcode-507-Perfect Number

    chenjx85

扫码关注云+社区

领取腾讯云代金券