算法 |
您所在的位置：网站首页 › 01规划问题求解 › 算法 |
算法
|
什么是动态规划
动态规划（dynamic programing）用于求解包含重叠子问题的最优化解的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解递推出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。 它的大概意思先将一件事情分成若干阶段，然后通过阶段之间的转移达到目标。由于转移的方向通常是多个，因此这个时候就需要决策选择具体向哪一个转移方向。 动态规划所要解决的事情通常是完成一个具体的目标，而这个目标往往是最优解。这种解题思路最初就是用来求最优解的，只不过有的时候顺便可以解决可行解，可行解总数等问题，这其实是动态规划的副产物。 示例题目 爬楼梯问题题目： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 输入: 2 输出: 2 解释:1阶+1阶 或 2阶有这两种方法可以爬到楼顶。 输入: 3 输出: 3 解释: 1阶+1阶+1阶，1阶+2阶 或 2阶+1阶 有三种方法可以爬到楼顶。 解题思路 1) 代码初步成型： 想要爬到第n层阶梯，必然是要从第n-1层阶梯或者第n-2层阶梯爬上来的。那么爬到第n-1层阶梯的方法数 + 爬到第n - 2层阶梯的方法数 = 爬到第n层阶梯的方法数。假设能有一个函数来计算爬到第n层阶梯的方法数，姑且给这个函数命名为dpFunc，那么爬到第n层阶梯的方法数可以用dpFunc(n)来表示。根据我们刚才的思路可以写出dpFunc(n) = dpFunc(n - 1) + dpFunc(n - 2)，有没有一点眼熟呢？ 不妨回想一下那个夏天，坐在考场上，顶着空白的大脑小心翼翼的低头看着那张已经被手汗浸湿的小抄是不是赫然写着如下代码？ 没错，这跟大学时代必考题目斐波那契数列不能说是非常相似吧，只能说是一模一样！ function climbStairs(n: number): number { const dpFunc = (n: number): number => { return dpFunc(n - 1) + dpFunc(n - 2) } return dpFunc(n) };2) 代码完善： 试想一下，如果递归运行这个函数，dp传入的值将没有界限，最终会导致栈溢出。所以我们需要设置一下这个递归函数的界限，至少我们要保证n - 1和n - 2这两个阶梯是存在的。已知dpFunc(1)=1，dpFunc(2)=2，当然dpFunc(0)的结果就是0咯。 function climbStairs(n: number): number { const dpFunc = (i: number): number => { if( i < 3 ) return i return dpFunc(i - 1) + dpFunc(i - 2) } return dpFunc(n) };3) 代码优化 以上得出的代码已经可以正常运行了，但经过尝试这个算法的效率非常的低。继续思考为啥会出现这样的情况呢？假设我们要计算dp(6)，来画一下整个运算的过程（如图） 不难发现这个算法目前还存在着大量的重复计算，怎么避免这些重复计算呢？给上图这个二叉树结构“剪个枝”好像是个办法。那么就引入一个记忆化搜索吧，典型的空间换时间。声明一个dp的数组，将计算过的dpFunc(n)，以n为下标来缓存起来。 function climbStairs(n: number): number { if (n < 3) return n const dp: number[] = new Array(n + 1) dp[0] = 0 dp[1] = 1 dp[2] = 2 const dpFunc = (i: number): number => { If (!dp[i]) { dp[i] = dpFunc(i - 1) + dpFunc(i - 2) } return dp[i] } return dpFunc(n) };4) 继续优化 这个题目的边界和遍历顺序 都是非常明确的，我们可以尝试使用for循环遍历来代替递归的写法。 function climbStairs(n: number): number { if (n < 3) return n const dp: number[] = new Array(n + 1) dp[0] = 0 dp[1] = 1 dp[2] = 2 for(let i = 3; i { if (!dp[x]) dp[x] = new Array(maze[0].length) if (typeof dp[x][y] === 'boolean') return dp[x][y] if (!maze[x][y]) { dp[x][y] = false return dp[x][y] } if (maze[x][y] === 9) { dp[x][y] = true return dp[x][y] } const arr = [[x, y+1], [x+1, y], [x, y-1], [x-1, y]].filter(point => { return point[0] >= 0 && point[0] < maze.length && point[1] >= 0 && point[1] < maze[0].length }) let res = false for(let i = 0; i < arr.length; i++) { res = canFindCheese(arr[i][0], arr[i][1], x, y) if (res) break } dp[x][y] = res return dp[x][y] } return canFindCheese(0, 0) }4) 尝试运行程序，打印dp数组，栈溢出，到底哪出了问题呢？分析计算过程可以发现，当“1”连成一圈的时候，老鼠也会不断的转圈，这样的计算过程就出现了无限套娃的情况，为了避免这个问题我们需要让老鼠不走重复坐标，当老鼠“走”过某坐标的时候做个标记，让老鼠不要再重复走当前坐标，问题就能解决了。 const findCheese = (maze) => { const dp = new Array(maze.length) const canFindCheese = (x, y) => { if (!dp[x]) dp[x] = new Array(maze[0].length) if (typeof dp[x][y] === 'boolean') return dp[x][y] if (!maze[x][y]) { dp[x][y] = false return dp[x][y] } if (maze[x][y] === 9) { dp[x][y] = true return dp[x][y] } const arr = [[x, y+1], [x+1, y], [x, y-1], [x-1, y]].filter(point => { return point[0] >= 0 && point[0] < maze.length && point[1] >= 0 && point[1] < maze[0].length }) dp[x][y] = false for(let i = 0; i < arr.length; i++) { dp[x][y] = canFindCheese(arr[i][0], arr[i][1]) if (dp[x][y]) break } return dp[x][y] } return canFindCheese(0, 0) }欢迎各位老师指导交流~ |
【本文地址】
今日新闻 |
推荐新闻 |