动态规划专题复习（一）计数问题

动态规划专题复习（一）计数问题

最近在复习算法，为明年的春招做准备，欢迎互关呀，共同学习，进步！

动态规划是一种算法思想，是将一个规模为N的问题分解为多个子问题，再根据子问题的解已得到原问题的解，往往用于优化递归问题，以减少递归方法的计算量，通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

以下问题均摘取自leetcode

一，计数问题

动态规划中的计数型问题就是利用动态规划的算法思想去计算出解决这个问题有多少种方法，比如，从起点走到终点，可以有多少条路径，注意，是多少条，而不是具体路线的描述。关于具体每一条路线的描述，那就是dfs的问题了。

在具体进行专题的复习之前，需要了解动态规划的几个概念，重叠子问题，状态转移方程，最优子结构，下边通过两道leetcode上的题目初步了解动态规划

1.斐波那契数列

暴力递归解

    /*** 直接递归版本的斐波那契数列* 直接暴力递归非常的耗时，时间复杂度成指数级增长* @param x* @return*/private static long[] array ;public static int fib(int x){if(x == 0 || x == 1){return x;}else{return fib(x - 1) + fib(x - 2);}}

学校的老师在说到递归这一章节的时候，斐波那契数列问题就是一个课堂上的经典例子，虽然递归的解法在代码可读性上很通俗易懂，但是效率却十分低下，所以被称之为暴力解法。

为何效率低下？

斐波那契数列递归树如下：

从递归树可以看到，有很多结果被重复的计算，就是说想要计算原问题 f(20)f(20)，我就得先计算出子问题 f(19)f(19) 和 f(18)f(18)，然后要计算 f(19)f(19)，我就要先算出子问题 f(18)f(18) 和 f(17)f(17)，以此类推。最后遇到 f(1)f(1) 或者 f(2)f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了，对于这种重复的计算，在动态规划中叫做重叠子问题。

记忆化搜索

通过上文的递归暴力解，我们知道了在递归中存在重叠子问题后，我们需要去解决这个重叠子问题，也就是减少重复计算

记忆化搜索也叫作备忘录递归解法，就是利用一个线性表存储递归过程中的计算结果，在需要使用到时直接从线性表中取，避免了重复的计算

    /*** 斐波那契额数列优化* 记忆化搜索【自上而下解决问题】* @param x* @return*/private static long[] array ;public static long fib2(int x){if(x == 0 || x == 1){return x;}else{if(array[x] == 0){array[x] = fib2(x - 1) + fib2(x - 2);}return array[x];}}

动态规划

记忆化搜索是自顶向下的解决问题，那么动态规划就是自底向上的解决问题，就是先从最基本的小问题开始往上推，直到推出我们的最终答案

我要求f(20)，我得知道f(19)和f(18)，依次类推，这是自顶向下，那当我们知道了f(0)和f(1)，同样道理，我们也能求出f(3)，在继续往上推，我们能利用f(3)和f(2)推出f(4)，依次类推，求出f(20)，这就是自底向上。

    /*** 【自下而上解决】* 【动态规划】* @param x* @return*/private static long[] array ;public static long fib3(int x){array[0] = 0;array[1] = 1;for(int i = 2;i <= x;i++){array[i] = array[i-2] + array[i-1];}return array[x];}

在这里引出状态转移方程的概念

什么是状态转移方程？

状态转移方程，我个人理解就是获得下一个状态的公式，比如，刚刚的斐波那契数列，如果我要获得f(3)，那么我就必须知道f(1) 和 f(2)，然后通过f(1) + f(2)，获得到f(3)，那么f(x) = f(x -1) + f(x - 2)就是状态转移方程

上面提到了动态规划的几个概念，重叠子问题，状态转移方程，再通过一道题目引出最优子结构这一概念

2.凑零钱

暴力递归

    public int coinChange(int[] coins, int amount) {if(amount == 0){return 0;}//硬币数量int result = Integer.MAX_VALUE;for(int coin : coins){if(amount - coin < 0){//当前所需金额小于零钱,跳过,尝试下一种零钱continue;}//递归中间结果int subResult = coinChange(coins,amount - coin);//子问题无解if(subResult == -1){continue;}//找出最优子结构result = Math.min(subResult + 1,result);}return result == Integer.MAX_VALUE ? -1 : result;  }

这里就有一个最优子结构的概念：原问题的解由子问题的最优解构成

记忆化搜索

    /*** 记忆化搜索* @param coins* @param amount* @return*/public int coinChange2(int[] coins, int amount) {int[] dp = new int[amount + 1];return coin(coins,amount,dp);}public int coin(int[] coins,int amount,int[] dp){if(amount == 0){return 0;}//查找、返回已经保存的结果if(dp[amount] != 0){return dp[amount];}int result = Integer.MAX_VALUE;for(int coin : coins){if(amount - coin < 0){//当前所需金额小于零钱,跳过continue;}//递归中间结果int subResult = coin(coins,amount - coin,dp);//子问题无解if(subResult == -1){continue;}result = Math.min(subResult + 1,result) ;}//保存中间结果dp[amount] = result == Integer.MAX_VALUE ? -1 : result;return dp[amount];}

动态规划

状态转移方程：f(x) = min{f(x - coins[0]),f(x - coins[1]),…} + 1

    /*** 动态规划* @param coins* @param amount* @return*/public int coinChange(int[] coins, int amount) {//状态转移方程：f(x) = min{f(x - coins[0]),f(x - coins[1]),...} + 1int max = amount + 1;int[] dp = new int[amount + 1];Arrays.fill(dp, max);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int j = 0; j < coins.length; j++) {if (coins[j] <= i) {//最优子结构dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}

接下来的题目会以解题为主，但是会有注释，文字描述就没那么多了

3.爬台阶

爬台阶这道题目和刚刚的斐波那契数列很相似，我们可以这么理解， 假设台阶数是n，爬上第n级台阶可以从n-1阶迈一步，也可以从n-2阶迈两步，那么，n-1阶可以从n-2阶迈一步达到，也可以从n-3阶迈两步达到，依次类推，那么就可以推出递推公式：f(x) = f(x - 1) + f(x - 2)，该递推公式也是状态转移方程，刚刚是从上往下的推，那么动态规划的自底向上就是一个逆向的过程

暴力递归

    public int climbStairs(int n) {if(n == 1 || n == 2){return n;}else{return climbStairs(n - 1) + climbStairs(n - 2);}}

记忆化搜索

    /*** 记忆化搜索*/private int[] array1;public int climbStairs1(int n){if(n <= 2){array1[n] = n;return array1[n];}else{if(array1[n] == 0) {array1[n] = climbStairs(n - 1) + climbStairs(n - 2);}return array1[n];}}

动态规划

    /*** 动态规划* 【自下向上】*/private int[] array;public int climbStairs2(int n) {array = new int[n+1];array[1] = 1;array[2] = 2;for(int i = 3;i <= n;i++){array[i] = array[i - 1] + array[i - 2];}return array[n];}

4.不同路径一

从起点 (x=0,y=0)(x=0,y=0) 出发，下一步只能向右或者向下到达第二点，向右则为 (x+1，y)(x+1，y) 向下则为 (x，y+1)(x，y+1)，一直到 (x=m，y=n)(x=m，y=n) 这个点则为结束点视为一条路径。因此，状态转移方程就是：f(x,y) = f(x + 1,y) + f(x, y + 1)。

暴力递归

    /*** 【暴力递归】* @param m* @param n* @return*/public int uniquePaths1(int m,int n){if(m <= 0 || n <= 0){return 0;}//只有一行或者只有一列，只能不断向右或者不断向下if(m == 1 || n == 1){return 1;}//两行两列if(m == 2 && n == 2){return 2;}//两行三列或者三行两列if(( m == 2 && n == 3 )||( m == 3 && n == 2 )){return 3;}int paths = 0;//向右的所有路径paths += uniquePaths1(m - 1,n);//向下的所有路径paths += uniquePaths1(m,n - 1);return paths;}

记忆化搜索

    /*** 【记忆化搜索】* @param m* @param n* @return*/public int uniquePaths3(int m ,int n){int[][] dp = new int[m + 1][n + 1];return uniquePaths2(m,n,dp);}public int uniquePaths2(int m,int n,int[][] dp){if(m <= 0 || n <= 0){return 0;}//只有一行或者只有一列，只能不断向右或者不断向下if(m == 1 || n == 1){return 1;}//两行两列if(m == 2 && n == 2){return 2;}//两行三列或者三行两列if(( m == 2 && n == 3 )||( m == 3 && n == 2 )){return 3;}if(dp[m][n] > 0){return dp[m][n];}//向右的所有路径dp[m - 1][n] = uniquePaths2(m - 1,n,dp);//向下的所有路径dp[m][n - 1] = uniquePaths2(m,n - 1,dp);dp[m][n] = dp[m][n -1] + dp[m - 1][n];return dp[m][n];}

动态规划

    /*** 不同路径* 【动态规划】* @param m* @param n* @return*/public int uniquePaths(int m, int n) {//状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - 1]int[][] f = new int[m][n];for(int i = 0;i<m;i++){for(int j = 0;j < n;j++){if(i == 0 || j == 0){f[i][j] = 1;}else{f[i][j] = f[i][j - 1] + f[i - 1][j];}}}return f[m - 1][n - 1];}

5.不同路径二

这个题目跟刚刚上边那个很相似，但是动态转移方程多了一个判断条件，就是判断o(x,y） 是不是等于1，如果等于1，则意味着有障碍物，无法进行动态转移方程

动态规划

    /*** 动态规划* @param obstacleGrid* @return*/public int uniquePathsWithObstacles(int[][] obstacleGrid) {//状态转移方程 f[i][j] = f[i - 1][j] + f[i][j - 1]//判断起点是否有障碍物if(obstacleGrid[0][0] == 1){return 0;}//可以走：1//有障碍：0obstacleGrid[0][0] = 1;//判断第一行for(int i = 1;i < obstacleGrid.length;i++){//前面没障碍 && 上一个可以通行if(obstacleGrid[i][0] == 0 && obstacleGrid[i-1][0] == 1){obstacleGrid[i][0] = 1;}else{obstacleGrid[i][0] = 0;}}//判断第一列for(int i = 1;i < obstacleGrid[0].length;i++){//前面没障碍 && 上一个可以通行if(obstacleGrid[0][i] == 0 && obstacleGrid[0][i-1] == 1){obstacleGrid[0][i] = 1;}else{obstacleGrid[0][i] = 0;}}//执行状态方程for (int i = 1; i < obstacleGrid.length; i++) {for (int j = 1; j < obstacleGrid[0].length; j++) {if (obstacleGrid[i][j] == 0) {obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];} else {obstacleGrid[i][j] = 0;}}}return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];}

6.不同的二叉搜索树一

二叉搜索树有个性质就是，左子节点 < 根节点 < 右子节点，所以在这道题目中，当左节点有n-1个节点时，右子节点为空，当头结点的值为i(1 < i < n)时，左子树由结点1—>i-1构成，右子树由结点i+1—>n构成，左子树的搜索二叉树个数为dp(i-1),右子树的搜索二叉树个数为dp(n - i);此时搜索二叉树总的个数为dp(i - 1) * dp(n - i)

暴力递归

    /*** 暴力递归* @param n* @return*/public int numTrees3(int n){if(n == 0 || n == 1){return 1;}int result = 0;for(int i = 0;i < n;i++){result += numTrees3(i) * numTrees3(n - i - 1);}return result;}

记忆化搜素

    /*** 记忆化搜索* @param n* @return*/public int numTrees2(int n){int[] dp = new int[n+1];dp[0] = 1;return numTrees1(n,dp);}public int numTrees1(int n,int[] dp) {if(dp[n] != 0){return dp[n];}int result = 0;for(int i = 0;i < n;i++){result += numTrees1(i,dp) * numTrees1(n - i - 1,dp);}dp[n] = result;return dp[n];}

动态规划

    /*** 动态规划* @param n* @return*/public int numTrees(int n) {int[] dp = new int[n + 1];//涉及乘法，0乘任何非0数都为0，一切为了构造下面递推式dp[0] = 1;//i：节点数for(int i = 1;i <= n; i++){//j：左子节点数for(int j = 0;j < i;j++){//状态转移方程：f(x) = f(0) * f(n - 1) + f(1) * f(n - 2) ....dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];}

接下来我会根据自己做到的题目进行归类，慢慢归类到这篇博客。