详谈电商网站建设四大流程,原创文章代写,大连建站企业,php mysql网站开发项目目录 0.动态规划问题
一.不同路径
1.题目描述
2.问题分析
3.代码实现
二.不同路径 II
1.题目描述
2.问题分析
3.代码实现
三.机器人双向走路
1.题目描述
2.问题分析
3.代码实现 0.动态规划问题
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问…目录 0.动态规划问题
一.不同路径
1.题目描述
2.问题分析
3.代码实现
二.不同路径 II
1.题目描述
2.问题分析
3.代码实现
三.机器人双向走路
1.题目描述
2.问题分析
3.代码实现 0.动态规划问题
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题,进行解决从而一步步获取最优解的处理算法
动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用
对于动态规划问题,大致可以分为以下几步:
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导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[][] dpnew int[m][n];for(int i0;in;i){dp[0][i]1;}for(int i1;im;i){dp[i][0]1;}for(int i1;im;i){for(int j1;jn;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~NN2,开始时机器人在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[i1][j-1];
所以递推公式为:dp[i][j]dp[i-1][j-1]dp[i1][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数组
对n5,steps3,start2,target3进行推导 [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-33.代码实现 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;} elsereturn 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);}}
