目录

0.动态规划问题

一.不同路径

1.题目描述

2.问题分析

3.代码实现

二.不同路径 II

1.题目描述

2.问题分析

3.代码实现

三.机器人双向走路

1.题目描述

2.问题分析

3.代码实现

---

0.动态规划问题

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

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

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

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

一.不同路径

1.题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

力扣:力扣

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 来表示。

力扣:力扣

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(机器人目前的位置)在内存循环

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);
        }
    }