服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - Java算法之动态规划详解

Java算法之动态规划详解

2023-11-01 01:42未知服务器之家 Java教程

①动态规划 动态规划 (Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动

①动态规划

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果

⓿动规五部曲

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

❶基础规划题

509. 斐波那契数

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 01 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n)

示例 1:

输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3:

输入:n = 4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
//动态规划
class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
//优化
class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

//递归
class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
}

70. 爬楼梯

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

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

示例 1:

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

示例 2:

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

本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于 2 部分之和

  1. 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
  2. 爬上 n−2 阶楼梯的方法数量,因为再爬2阶就能到第n阶

所以我们得到公式 dp[n] = dp[n−1] + dp[n−2],同时需要初始化 dp[0]=1 和 dp[1]=1

时间复杂度:O(n)

class Solution {
    public int climbStairs(int n) {
        int dp[] = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

示例 2:

输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。

  1. 确定dp数组以及下标的含义
  • dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]
  1. 确定递推公式
  • 有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]
    • dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
    • dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
  • 那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?
  • 一定是选最小的,所以 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  1. dp数组如何初始化

题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达第 0 、1个台阶是不花费的,但从 第0 个台阶往上跳的话,需要花费 cost[0]。所以初始化 dp[0] = 0,dp[1] = 0;

  1. 确定遍历顺序

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
       return dp[n];
    }
}

118. 杨辉三角

给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中,每个数是它左上方和右上方的数的和。

Java算法之动态规划详解

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if(j == 0 || j == i) row.add(1);
                else row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
            }
            res.add(row);
        }
        return res;
    }
}

62. 不同路径

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

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

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

示例 1:

Java算法之动态规划详解

输入:m = 3, n = 7
输出:28

示例 2:

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

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

我们令 dp[i][j] 是到达 i, j 最多路径

动态方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]

注意,对于第一行 dp[0][j],或者第一列 dp[i][0],由于都是在边界,所以只能为 1

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        //初始化
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                //到达i行j列的路径条数
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

63. 不同路径 II

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

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

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

网格中的障碍物和空位置分别用 10 来表示。

示例 1:

Java算法之动态规划详解

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

示例 2:

Java算法之动态规划详解

输入:obstacleGrid = [[0,1],[0,0]]
输出:1

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int dp[][] = new int[m][n];
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){
            dp[i][0] = 1;
        }
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++){
            dp[0][j] = 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];
    }
}

343. 整数拆分

剑指 Offer 14- I. 剪绳子 - 力扣(Leetcode)

给定一个正整数 n ,将其拆分为 k正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

返回 你可以获得的最大乘积

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

动规五部曲,分析如下:

  1. 确定dp数组以及下标的含义

dp[i]:分拆数字 i,可以得到的最大乘积为dp[i]

  1. 确定递推公式

i ≥ 2 时,假设对正整数 i 拆分出的第一个正整数是 j1 ≤ j < i),则有以下两种方案:

  • i 拆分成 ji−j 的和,且 i−j 不再拆分成多个正整数,此时的乘积是 j×(i−j)
  • i 拆分成 ji−j 的和,且 i−j 继续拆分成多个正整数,此时的乘积是 j×dp[i−j]

递推公式:dp[i]=max{dp[i], j×(i−j), j×dp[i−j]}

  1. dp的初始化

初始化 dp[2] = 1

  1. 确定遍历顺序
  • 2 < i <= n
  • 1 < j < i
for (int i = 3; i <= n ; i++) {
    for (int j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}
  1. 举例推导dp数组

。。。

class Solution {
    public int integerBreak(int n) {
        int dp[] = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            for(int j = 1; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        } 
        return dp[n];
    }
}

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

每段长度取3最好

class Solution {
    public int cuttingRope(int n) {
        if(n == 2)
            return 1;
        if(n == 3)
            return 2;
        long res = 1;
        while(n > 4){
            //每一段取3进行累积
            res *= 3;
            res = res % 1000000007;
            n -= 3;
        }
        return (int)(res * n % 1000000007);//最后一段不能被3整除,累积上再取mod
    }
}

96. 不同的二叉搜索树

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

Java算法之动态规划详解

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

  1. 确定dp数组(dp table)以及下标的含义

dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]。

  1. 确定递推公式

假设一共i个节点,对于根节点为j时,左子树的节点个数为j-1,右子树的节点个数为i-j

对于根节点为j时,其递推关系, dp[i] = ∑(1<=j<=i) dp[左子树节点数量] * dp[右子树节点数量]j是头结点的元素,从1遍历到i为止。

所以递推公式:dp[i] += dp[j - 1] * dp[i - j];

  1. dp数组如何初始化
  • dp[0] = 1;
  • dp[1] = 1;
  1. 确定遍历顺序
for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        
    }
}
class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];   
            }
        }
        return dp[n];
    }
}

338. 比特位计数

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1:

输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

进阶:

  • 很容易就能实现时间复杂度为 O(nlogn) 的解决方案,你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗?
  • 你能不使用任何内置函数解决此问题吗?(如,C++ 中的 __builtin_popcount

动态规划法

  1. 如果这个数是偶数,那么其二进制中1的个数一定和其1/2的数二进制中1的个数一样,因为1/2就相当于右移1位,即把偶数的最后一个0去掉,不会影响1的个数。
    • res[i] = res[i / 2]
  2. 如果这个数是奇数:那么其二进制中1的个数一定是其上一个偶数二进制1的个数+1,因为就相当于将上一个偶数二进制的最后1位的0变成1
    • res[i] = res[i - 1] + 1—>res[i] = res[i / 2] + 1
  3. 上述两种情况可以合并成:res[i]的值等于 res[i/2]的值加上 i % 2
    • res[i / 2] + (i % 2)—>res[i >> 1] + (i & 1)
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) {
                // 奇数:当前奇数的1的个数一定比上一个偶数+1
                res[i] = res[i - 1] + 1;
            } else {
                // 偶数:偶数1的个数一定和其1/2的偶数1的个数一样
                res[i] = res[i / 2];
            }
        }
        return res;
    }
}

//优化
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下:

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2:

输入:n = 25
输出:1389537 

class Solution {
    int[] dp = new int[38]; //用于防止重复计算
    public int tribonacci(int n) {
        if(n == 0) return 0;
        if(n <= 2) return 1;
        int a = 0, b = 1, c = 1;
        for(int i = 3; i <= n; i++){
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }
}

❷01背包问题

延伸 · 阅读

精彩推荐