动态规划——unique-paths-ii

题目描述:

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as1and0respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is2.

Note: m and n will be at most 100.

递归例程:
public class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        if(grid == null||grid.length == 0||grid[0].length == 0)
            return 0;
        int row=grid.length;
        int col=grid[0].length;
        return help(grid,0,0,row,col);
    }
    public int help(int[][] grid,int i,int j,int row,int col)
        {
        if(i == row-1&&j == col-1)
            return 1;
        if(grid[i][j] == 1)
            return 0;
        if(i == row-1)
            return help(grid,i,j+1,row,col);
        if(j == col-1)
            return help(grid,i+1,j,row,col);
        else
            return help(grid,i+1,j,row,col)+help(grid,i,j+1,row,col);
    }
}


DP例程:
 public int uniquePathsWithObstacles(int[][] grid) {
        if(grid == null||grid.length == 0||grid[0].length == 0)
            return 0;
        int row=grid.length;
        int col=grid[0].length;
        int[][] dp=new int[row][col];
        dp[row-1][col-1]=1;
        if(grid[row-1][col-1] == 1)
            dp[row-1][col-1]=0;
        //最下行初始化
        for(int j=col-2;j>=0;j--)
            {
            if(grid[row-1][j] == 1)
                dp[row-1][j]=0;
            else
                dp[row-1][j]=dp[row-1][j+1];
        }
        //最右行初始化
        for(int i=row-2;i>=0;i--)
            {
            if(grid[i][col-1] == 1)
                dp[i][col-1]=0;
            else
                dp[i][col-1]=dp[i+1][col-1];
        }
        //general
        for(int i=row-2;i>=0;i--)
            {
            for(int j=col-2;j>=0;j--)
                {
                if(grid[i][j] == 1)
                    dp[i][j]=0;
                else
                    dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[0][0];
    }


### C++ 中使用动态规划进行路径计数 在解决路径计数问题时,动态规划是一种非常有效的方法。对于从二维数组的左上角走到右下角的问题,可以通过构建一个同样大小的二维表来存储到达每个位置的不同路径数量。 #### 动态规划解法的核心思路 创建一个 `dp` 表格,其中 `dp[i][j]` 表示从起点 (0, 0) 到达坐标 `(i, j)` 的不同路径数目。由于只能向下或向右走,则有: - 当位于第一行时 (`i=0`) ,只有一种方式进入该列; - 同样地,在最左侧的一列里(`j=0`)也仅存在一条路线可抵达各单元格; - 对于其他任意一点`(i,j)`而言,可以从上方(i−1,j) 或者左边(i,j−1) 来到这里[^2]。 因此状态转移方程如下所示: \[ dp[i][j]=\begin{cases} 1 & \text{if } i==0 \text{ or } j==0 \\ dp[i-1][j]+dp[i][j-1] & \text{otherwise} \end{cases}\] 下面是具体的实现代码: ```cpp #include <iostream> using namespace std; int uniquePaths(int m, int n){ // 创建并初始化DP表格 int dp[m][n]; for(int i = 0; i<m ; ++i){ for(int j = 0;j<n;++j){ if(i == 0 || j == 0){ dp[i][j] = 1; } else{ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[m-1][n-1]; } // 测试函数 void test(){ cout << "The number of paths from top-left to bottom-right is: "; cout<<uniquePaths(3,7)<<endl; } int main() { test(); return 0; } ``` 此程序定义了一个名为 `uniquePaths()` 的功能,它接收两个参数——网格的高度和宽度,并返回可能的独特路径总数。测试部分展示了如何调用这个函数以及预期的结果输出。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值