Java之动态规划之机器人移动

ゞ浴缸里的玫瑰 2024-03-26 10:45 53阅读 0赞

**目录**

0.动态规划问题

一.不同路径

1.题目描述

2.问题分析

3.代码实现

二.不同路径 II

1.题目描述

2.问题分析

3.代码实现

三.机器人双向走路

1.题目描述

2.问题分析

3.代码实现

--------------------

## 0.动态规划问题 ##

**动态规划**(**D**ynamic **P**rogramming)算法的核心思想是:将大问题划分为小问题,进行解决，从而一步步获取最优解的处理算法

动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用

对于**动态规划问题**,大致可以分为以下几步:

1.  确定dp数组（dp table）以及下标的含义
2.  确定递推公式
3.  dp数组如何初始化
4.  确定遍历顺序
5.  举例推导dp数组

## 一.不同路径 ##

### 1.题目描述 ###

> 一个机器人位于一个 `m x n`网格的左上角 （起始点在下图中标记为 “Start” ）。
> 
> 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
> 
> 问总共有多少条不同的路径？

力扣:[力扣][Link 1]

![5711002a977643d983f0cb169b5e314b.png][]

### 2.问题分析 ###

**1.确定dp数组（dp table）以及下标的含义**

**dp\[i\]\[j\]:机器人走到(i,j)网格的位置有dp\[i\]\[j\]种方法**

**2.确定递推公式**

**因为机器人每次只能向下或者向右移动,所以机器人到达(i,j)的位置只存在两种情况**

**第一种:从上边的格子走过来,一共有dp\[i-1\]\[j\]种情况**

**第二种:从左边的格子走过来,一种有dp\[i\]\[j-1\]种情况**

**所以dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\]**

**3.dp数组如何初始化**

**由递推公式可以看出来,至少初始化第一行和第一列,因为机器人只能左走和下走,所以第一行和第一列只可能有一种情况到达(一直左走或者一直向下走)**

**4.确定遍历顺序**

**由递推公式可以看出来,从左到右,从上到下**

**5.举例推导dp数组**

**对m = 3, n = 7进行推导**

> \[1, 1, 1, 1, 1, 1, 1\]  
> \[1, 2, 3, 4, 5, 6, 7\]  
> \[1, 3, 6, 10, 15, 21, 28\]

### **3.代码实现** ###

public int uniquePaths(int m, int n) {
            int[][] dp=new int[m][n];
            for(int i=0;i<n;i++){
                dp[0][i]=1;
            }
            for(int i=1;i<m;i++){
                dp[i][0]=1;
            }
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }
            }
            return dp[m-1][n-1];
    
        }

## 二.不同路径 II ##

### 1.题目描述 ###

> 一个机器人位于一个 `m x n` 网格的左上角 （起始点在下图中标记为 “Start” ）。
> 
> 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
> 
> 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
> 
> 网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。

力扣:[力扣][Link 2]

![5eece26e980f46b4ae7d56c1398c98e4.png][]

### 2.问题分析 ###

这一题与上一题的区别就是多了障碍,有障碍的地方右走是无法到达的,但是可以从上方到达(不是第一行),知道这个易解

**1.确定dp数组（dp table）以及下标的含义**

**dp\[i\]\[j\]:机器人走到(i,j)网格的位置有dp\[i\]\[j\]种方法**

**2.确定递推公式**

**因为机器人每次只能向下或者向右移动,所以机器人到达(i,j)的位置(左方不存在任何障碍)只存在两种情况**

**第一种:从上边的格子走过来,一共有dp\[i-1\]\[j\]种情况**

**第二种:从左边的格子走过来,一种有dp\[i\]\[j-1\]种情况**

**所以dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\]**

**左方一格存在障碍的时候,只能从上方到来(默认障碍位置到达的方法dp\[i\]\[j\]为0即可)**

**3.dp数组如何初始化**

**由递推公式可以看出来,至少初始化第一行和第一列,当右方存在障碍,第一行和第一列只可能有一种情况到达,当上方或者左方存在障碍的时候,障碍之后的路没有情况可以到达**

for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) {
                dp[i][0] = 1;
            }
            for (int i = 0; i < n && obstacleGrid[0][i] == 0; ++i) {
                dp[0][i] = 1;
            }

**4.确定遍历顺序**

**由递推公式可以看出来,从左到右,从上到下**

**5.举例推导dp数组**

**对obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]进行推导**

> \[1, 1, 1\]  
> \[1, 0, 1\]  
> \[1, 1, 2\]

### **3.代码实现** ###

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            if(obstacleGrid[0][0] == 1)
                return 0;
    
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) {
                dp[i][0] = 1;
            }
            for (int i = 0; i < n && obstacleGrid[0][i] == 0; ++i) {
                dp[0][i] = 1;
            }
    
            for (int i = 1; i < m; ++i) {
                for (int j = 1; j < n; ++j) {
                    if (obstacleGrid[i][j] == 0)
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    
                }
    
            }
    
            return dp[m-1][n-1];
    
        }

## 三.机器人双向走路 ##

### 1.题目描述 ###

> 假设有排成一行的N个位置，记为1~N，（N>=2）,开始时机器人在start位置，有如下约束
> 
>  *  机器人在1位置，下一步只能走到2位置
>  *  机器人在N位置，下一步只能走到N-1位置
>  *  机器人在其他位置，下一步能走左边，也能走右边  
>     求机器人从start位置经过k步到达target位置的方法数。

### 2.问题分析 ###

这一题从二维变成了一维,显然是增加了难度的,因为可能存在在一个位置上来回移动的情况,所以dp数组和前几题有明显的的不一样,**采用从后到前的推导方式,从target位置推导到start位置**

**1.确定dp数组（dp table）以及下标的含义**

**dp\[i\]\[j\]的含义:机器人剩余j步,在i位置走到target位置可以有dp\[i\]\[j\]中方法数**

**2.确定递推公式**

**因为机器人只能向左或是向右移动,所以dp\[i\]\[j\]可以有两种方式推导出来**

**从左格移动到i位置:dp\[i\]\[j\]=dp\[i-1\]\[j-1\];**

**从右格移动到i位置:dp\[i\]\[j\]=dp\[i+1\]\[j-1\];**

**所以递推公式为:dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+dp\[i+1\]\[j-1\]**

**但是存在两种特殊情况,当机器人位于1位置的时候,只能向右移动到2位置**

**当机器人位于n位置的时候,只能向左移动到n-1位置**

if (i == 1) {
                        dp[i][j] = dp[2][j - 1];
                    } else if (i == n) {
                        dp[i][j] = dp[n - 1][j - 1];
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1];
                    }

**3.dp数组如何初始化**

**当机器人剩余0步的时候,已经在target位置的时候,这种情况下到达dp显然是1中情况**

**4.确定遍历顺序**

**由下图可以看出,遍历顺序应该先从左到右,然后从上到下进行遍历,也就是j(剩余的步数)在外层循环,i(机器人目前的位置)在内存循环**

![99d7cc5110f94b078084c9c0d2e7d10b.png][]

**5.举例推导dp数组**

**对n=5,steps=3,start=2,target=3进行推导**

>     [0, 1, 0, 2]
>     [1, 0, 2, 0]
>     [0, 1, 0, 3]
>     [0, 0, 1, 0]
>     [0, 0, 0, 1]

也就是这三种情况

>     1).2->1,1->2,2->3 
>     2).2->3,3->2,2->3 
>     3).2->3,3->4,4->3

### **3.代码实现** ###

public int move(int n, int steps, int start, int target) {
            int[][] dp = new int[n + 1][steps + 1];
            //剩余的步数为0,当前位置为target时
            dp[target][0] = 1;
    
            for (int j = 1; j <= steps; ++j) {
                for (int i = 1; i <= n; ++i) {
                    if (i == 1) {
                        dp[i][j] = dp[2][j - 1];
                    } else if (i == n) {
                        dp[i][j] = dp[n - 1][j - 1];
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1];
                    }
    
                }
            }
            return dp[start][steps];
        }

**回溯代码**

/**
         * @param n      能够到达位置的最大值(1--n位置移动)
         * @param steps  剩余需要移动的步数
         * @param start  当前开始所处的位置
         * @param target 需要到达的目标位置
         * @return 一共到达目标位置的方法数
         */
        public int move(int n, int steps, int start, int target) {
            if (steps == 0) {
                if (start == target) {
                    return 1;
                } else
                    return 0;
            } else if (start == 1) {
                return move(n, steps - 1, 2, target);
            } else if (start == n) {
                return move(n, steps - 1, n - 1, target);
            } else {
                return move(n, steps - 1,
                        start + 1, target) + move(n, steps - 1, start - 1, target);
            }
        }

[Link 1]: https://leetcode.cn/problems/unique-paths/
[5711002a977643d983f0cb169b5e314b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f3927a2ea35746fe87bb4c609fddb261.png
[Link 2]: https://leetcode.cn/problems/unique-paths-ii/
[5eece26e980f46b4ae7d56c1398c98e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4cb52cad54744cc88ab222ba540c5e18.png
[99d7cc5110f94b078084c9c0d2e7d10b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1975135e014040938cd6b5fcba56f8db.png