【数据结构与算法】动态规划经典题总结[leetcode]

爬楼梯

** 五星 **
LeetCode:爬楼梯

题目描述:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

思想:

1.动态规划,时间O(n)
到达某一个台阶方法数,等于抵达前两个台阶的方法数之和。

可使用滚动数组来优化,仅保存三个变量,使得空间复杂度为O(1)
2.矩阵快速幂
时间:O(log(n));空间:O(1)
3.斐波那契数列通项公式
时间:O(log(n));空间:O(1)

代码:

滚动数组,仅保存三个变量

class Solution {
    public int climbStairs(int n) {
        int r1=1,r2=2,res=n;//r1和r2分别表示当前位置的前两个数
        for(int i = 3;i<=n;++i){
            res = r1 + r2;
            r1 = r2;
            r2 = res;
        }
        return res;
    }
}

自底向上动态规划法

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];//存储每一个台阶的方法数
        dp[0]=1;//0号位是多余的,故数组要分配n+1项
        dp[1]=1;
        for(int i = 2;i<=n;++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

矩阵快速幂:

    public int climbStairs3(int n) {
        if (n < 2) return 1;
        int[][] q = new int[][]{{1, 1}, {1, 0}};
        q = pow(q, n - 2);
        return 2 * q[0][0] + q[0][1];
    }

    //计算一个矩阵的n次方
    private int[][] pow(int[][] q, int n) {
        int[][] res = new int[][]{{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) res = multiply(res, q);
            n >>= 1;
            q = multiply(q, q);
        }
        return res;
    }

    private int[][] multiply(int[][] a, int[][] b) {
        int[][] res = new int[2][2];
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                res[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return res;
    }

通项公式:

    public int climbStairs2(int n) {
        double sqrt5 = Math.sqrt(5);
        double res = (Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1)) / sqrt5;
        return (int) res;
    }

买卖股票的最佳时机

LeetCode:买卖股票的最佳时机

题目描述:

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

示例:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

思想:

dp思想

  • 记录【今天之前买入的最小值】
  • 计算【今天之前最小值买入,今天卖出的获利】,也即【今天卖出的最大获利】
  • 比较【每天的最大获利】,取最大值即可

代码:

class Solution {
    public int maxProfit(int[] prices) {
        int L = prices.length;
        if(L == 0){
            return 0;
        }
        //min表示当前位置之前的最小值
        int min = prices[0],maxProfit = 0;
        for(int i=1;i<L;++i){
            //prices[i]-min表示当前位置抛售可获得的最大利润
            maxProfit = Math.max(maxProfit,prices[i]-min);
            min = Math.min(prices[i],min);
        }
        return maxProfit;
    }
}

最长回文子串

LeetCode:最长回文子串

题目描述:

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

思想:

  • 动态规划,用boolean[][] dp记录每一对字符是否相等;
  • 双循环遍历所有子串情况,每次遍历时,当前子串首尾相等且内层-1字符串dp值为true,则记录dp值为true;全部遍历完,取最长,即为最长子串;
  • 临界条件很复杂,最好在循环之前把长度小于2的情况剔除;条件中有一个i-j<3,因为小于3且首尾相等的子串一定是回文串,不需要再往内层再判断dp。

代码:

class Solution {
    public String longestPalindrome(String s) {

        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int i,j,max=0,m=0,n=0;
        if(len<2) return s;
        for(i=0;i<len;++i){
            for(j=0;j<=i;++j){
                if(s.charAt(i) == s.charAt(j)&&(i-j<3||dp[j+1][i-1])){
                    dp[j][i]=true;
                    if(i-j>max){
                        max = i-j;
                        m=j;n=i;
                    }
                }else{
                    dp[j][i]=false;
                }
            }
        }
        return s.substring(m,n+1);
    }
}

不同路径

LeetCode:不同路径

题目描述:

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

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

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

示例:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

思想:

方法1:
dp思想,每一个格子的路径数,等于上面一格+左边一格的路径数之和;

注意i=0和j=0时,所有格的dp值为1,直接判断一下赋值1即可,不用再算,太麻烦。
方法2:
对方法1的优化。可以使用一维dp数组 dp[n] 。
因为每次累加时(假设逐行遍历),只使用了一行的数据,并没有涉及到前面几行,所以考虑缩减为单维dp数组。
方法3:
数学方法。总共需要 m+n-2 步到达终点,需要向下走 m-1 步,仔细想想,这实际上是一个“组合”问题,在 Y=m+n-2 次移动中取 X=m-1 个向下的移动,C(Y,X) 即为结果。
组合公式的代码实现如下:

for(int i=1;i<m;++i){
    res = res * (Y - X +i) / i;
}

注意:

  1. 有除法,但是不可能出现非整除的情况,结果必是整数。但是如果这样写:res *= (Y - X +i) / i 就可能出现错误,除不尽。

  2. res * (Y - X +i)可能超出int范围,所以要用 long 来定义 res。

代码:

方法1:

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

方法2:

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

方法3:

class Solution {
    public int uniquePaths(int m, int n) {
        int Y = m + n -2;
        int X = m - 1;
        long res = 1;
        for(int i=1;i<m;++i){
            res = res * (Y - X +i) / i;
        }
        return (int) res;
    }
}

不同路径2

LeetCode:不同路径 II

题目描述:

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

示例:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

思想:

跟上一题差不多,加一点判断条件;

注意:这题i=0和j=0时,dp值不全为1,可能是0,因为前面可能有障碍物。判断条件需要做一些调整。

代码:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(obstacleGrid[i][j]==1){
                    obstacleGrid[i][j] = 0;
                }else if(i==0&&j==0){
                    obstacleGrid[i][j] = 1;
                }else{
                    obstacleGrid[i][j] = (i==0?0:obstacleGrid[i-1][j]) + (j==0?0:obstacleGrid[i][j-1]);
                }
            }
        }
        return obstacleGrid[m-1][n-1];
    }
}

最小路径和

LeetCode:最小路径和

题目描述:

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思想:

动态规划,可以用原数组作为dp数组

代码:

class Solution {
    public int minPathSum(int[][] grid) {
        int i=0,j=0;
        for(i=0;i<grid.length;++i){
            for(j=0;j<grid[0].length;++j){
                if(i>0&&j>0){
                    grid[i][j]+= Math.min(grid[i-1][j],grid[i][j-1]);
                }else{
                    grid[i][j]+= (i==0?0:grid[i-1][j]) + (j==0?0:grid[i][j-1]);
                }
            }
        }
        return grid[i-1][j-1];
    }
}

三角形最小路径和

LeetCode:三角形最小路径和

题目描述:

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

示例:

例如给定三角形
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

思想:

自底向上,修改dp数组

代码:

第一种方法:在原数组上修改。这样貌似效率不高。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i=triangle.size()-2;i>=0;--i){
            for(int j=0;j<i+1;++j){
                triangle.get(i).set(j,triangle.get(i).get(j)+Math.min(triangle.get(i+1).get(j+1),triangle.get(i+1).get(j)));
            }
        }
        return triangle.get(0).get(0);
    }
}

第二种方法:设置dp数组,修改dp数组;注意这很巧妙,每一次修改都不会影响下次循环的判断;其次,每次循环,最后一个数都不会修改它,直到最后一轮,加上顶部的数,得到最终结果dp[0]。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] dp=new int[len];
        for(int i=0;i<len;++i){
            dp[i]=triangle.get(len-1).get(i);
        }
        for(int i=len-2;i>=0;--i){
            for(int j=0;j<i+1;++j){
                dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}
原文地址:https://www.cnblogs.com/buptleida/p/12528208.html