There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Solution

\(dp[i][j]\) 表示到位置 \(i,j\) 的方案数,很明显的转移方程:

\[dp[i][j] = dp[i-1][j]+dp[i][j-1] \]

对于初始化,由于只能右或者下,所以边界的方案数都为 \(1\):

\[dp[i][0] = dp[0][j] = 1 \]

点击查看代码
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long dp[105][105];
        if(m==1&&n==1)return 1;
        for(int i=0;i<m;i++)dp[i][0]=1;
        for(int j=0;j<n;j++)dp[0][j]=1;
        for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if(i==0 && j==0)continue;
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }
        return (dp[m-1][n-1]);
    }
};

标签智能推荐:

最大和的连续子数组合计

=start;i&lt;=end;i++){sum+=nums[i];}returnsum;}算法三:也是动态规划,使用一位数组表示,每个节点是保存当前直接前的最大值,leetcode过了~~publicstaticintmaxSubArray(int[]nums){int[]dp=newint[nums.length];dp[0]=nums[0];intsum=nums[0];for(inti=

188. 买卖股票的最佳时机 IV dp

&lt;int&gt;&amp;prices){//dp[i][0]和dp[i][1]分别表示在第i次交易中买入和卖出时各自的最大收益vector&lt;vector&lt;int&gt;&gt;dp(k+1,vector&lt;int&gt;(2,0));for(inti=0;i&lt;=k;i++){dp[i][0]=INT_MIN;}for(autop:prices){for(inti=1;

0123-买卖股票最佳时机III

*5for_inrange(len(prices))]dp[0][1]=-prices[0]dp[0][3]=-prices[0]foriinrange(1,len(prices)):dp[i][0]=dp[i-1][0]dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]

剪绳子 求最大乘积问题

]*dp[1],dp[4]*dp[2],dp[3]*dp[3],6}=3*3//dp[7]=max{dp[6]*dp[1],dp[5]*dp[2],dp[4]*dp[3],7}=12=2*3*2//dp[8]=max{dp[7]*dp[1],dp[6]*dp[2],dp[5]*dp[3],dp[4]*dp[4],8}=3*3*2//。。。if(n&lt;4)returnn-1;std::vecto

509. 斐波那契数

ps://leetcode-cn.com/problems/fibonacci-number/)//动态规划:1)确定DP数组使用一维数组dp[i]表示第i个数字,2)确定递推公式3)确定初始状态4)确定遍历过程5)模拟结果以便于debug//时间复杂度O(n),空间复杂度O(n)classSolution{//完整dp解法publicintfib(intn){if(n==0){return0;}

Dynamitic Programming journey

PostwithhisDPjourney.Asthebeginner,thebloggersaid"Isolved/read45DPproblemsofdifferentpatternsin4days(yes,youmightthinkthatisquiteslow)."https://leetcode.com/discuss/general-discussion/475924/My-experi

509. 斐波那契数

nt[]dp=newint[n+1];dp[0]=0;dp[1]=1;for(inti=2;i&lt;=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}}/***时间复杂度O(n)*空间复杂度O(n)*/优化1——滚动数组减小空间复杂度classSolution{publicintfib(intn){/***动态规划*fib(n)只与fib(n-1)和fib(

32、最长有效括号 | 算法(leetode,附思维导图 + 全部解法)300题

2)核心://1)我们用dp[i]表示以i结尾的最长有效括号//2.1)若s[i]为(,则dp[i]必然等于0,因为不可能组成有效的括号//2.2)若s[i]为),//2.2.1)且当s[i-1]为(,则dp[i]=dp[i-2]+2;//2.2.2)且当s[i-1]为)&amp;&amp;s[i-dp[i-1]-1]为(,则dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]。for(

[LeetCode] 1039. Minimum Score Triangulation of Polygon 多边形三角形化的最小得分

vector&lt;int&gt;&gt;dp(n,vector&lt;int&gt;(n));for(inti=n-1;i&gt;=0;--i){for(intj=i+1;j&lt;n;++j){for(intk=i+1;k&lt;j;++k){dp[i][j]=min(dp[i][j]==0?INT_MAX:dp[i][j],dp[i][k]+A[i]*A[k]*A[j]+dp[k][j]);

每日一练(22):连续子数组的最大和

nmaxSum;}方法二:动态规划(DP方程)思路和算法最原始的动态规划状态:dp[i]:以第i个数结尾的和的最大值转移:若dp[i-1]&lt;0,则以第i个数结尾的和的最大值为第i个数本身若dp[i-1]&gt;0,则以第i个数结尾的和的最大值为的dp[i-1]与dp[i-1]+nums[i]中的较大者避免遍历dp数组,每次比较dp更新结束后比较res与dp[i]的大小作为返回值intmaxS