LeetCode 576. 出界的路径数

ゝ一世哀愁。 2023-07-05 13:09 8阅读 0赞

### 解题思路 ###

这题其实用逆向思维更简单。dp\[i\]\[j\]\[k\]表示从外界走k步能到达(i,j)。  
状态转移很简单，无非就是dp\[i\]\[j\]\[k\]+=(4个方向的k-1步)。

### 代码 ###

#include <bits/stdc++.h>
    class Solution { 
    public:
       const int mod=1e9+7;
        int findPaths(int m, int n, int N, int l, int r) { 
    
            l++;
            r++;
           int dp[m+2][n+2][N+2];
           memset(dp,0,sizeof(dp));
           for(int i=0;i<=m;i++)
           { 
               dp[i][0][0]=1;
               dp[i][n+1][0]=1;
           }
           for(int j=0;j<=n;j++)
           { 
               dp[0][j][0]=1;
               dp[m+1][j][0]=1;
           }
          for(int k=1;k<=N;k++){ 
            for(int i=1;i<=m;i++)
            { 
                for(int j=1;j<=n;j++)
                { 
                    dp[i][j][k]=(dp[i-1][j][k-1]+dp[i][j-1][k-1])%mod+(dp[i+1][j][k-1]+dp[i][j+1][k-1])%mod;
                    dp[i][j][k]%=mod;
                }
            }
          }
           
           int ans=0;
           for(int k=1;k<=N;k++)
           { 
               ans+=dp[l][r][k];
               ans%=mod;
           }
            return ans;
        }
       
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 576. 出界的路径数

解题思路这题其实用逆向思维更简单。dp\[i\]\[j\]\[k\]表示从外界走k步能到达(i,j)。状态转移很简单，无非就是dp\[i\]\[j\]\[k\]+

ゝ一世哀愁。/ 2023年07月05日 13:09/ 0 赞/ 9 阅读

相关 Leetcode 576. 出界的路径数

Leetcode 576. 出界的路径数 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn

刺骨的言语ヽ痛彻心扉/ 2023年02月11日 07:16/ 0 赞/ 102 阅读

相关 576-二分搜索算法(折半查找)

如果数据序列是无序的，我们采用的是线性搜索，时间复杂度是O(n） ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_s

电玩女神/ 2022年09月11日 14:21/ 0 赞/ 185 阅读

相关 576 出界的路径数（动态规划-递推）

1. 问题描述：给你一个大小为 m x n 的网格和一个球。球的起始坐标为 \[startRow, startColumn\] 。你可以将球移到在四个方向上相邻的单元格内（

左手的ㄟ右手/ 2022年08月31日 11:10/ 0 赞/ 171 阅读

相关 leetcode 576. Out of Boundary Paths | 576. 出界的路径数（暴力递归-＞傻缓存-＞dp）

题目 [https://leetcode.com/problems/out-of-boundary-paths/][https_leetcode.com_problems

偏执的太偏执、/ 2022年08月28日 08:56/ 0 赞/ 151 阅读

相关 leetcode 576. Out of Boundary Paths K步内出界的次数之和 + DP动态规划

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you c

约定不等于承诺〃/ 2022年06月03日 04:39/ 0 赞/ 134 阅读

相关 leetcode 简化路径

给定一个文档 (Unix-style) 的完全路径，请进行路径简化。 > 例如， > path = "/home/", => "/home" > path = "/a

谁借莪１个温暖的怀抱￠/ 2022年03月02日 16:36/ 0 赞/ 223 阅读

相关 LeetCode中的题-----不同路径

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5u

快来打我*/ 2022年02月14日 06:52/ 0 赞/ 172 阅读

相关 576. Out of Boundary Paths

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you c

Love The Way You Lie/ 2022年01月12日 10:53/ 0 赞/ 158 阅读

相关【LeetCode每天一题】Unique Paths(唯一的路径数)

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

喜欢ヅ旅行/ 2021年12月15日 14:21/ 0 赞/ 167 阅读