乐趣区

关于java:Java算法系列动态规划算法二

jiezi

【写在后面】

“Java 算法系列”目录如下（更新 ing）：

  • 数据结构相干算法
  • 八大排序算法：冒泡排序、抉择排序、插入排序、希尔排序、疾速排序、归并排序、基数排序、堆排序
  • 四大查找算法：线性查找、二分查找、插值查找、斐波那契查找
  • 九大罕用算法：分治算法、动静布局算法、KMP 算法、贪婪算法、Prim 算法、Kruskal 算法、Dijkstra 算法、Floyd 算法、骑士环游回溯算法

本篇为 九大罕用算法 之动静布局算法。

〇、根本介绍

动静布局算法的 核心思想 是：将大问题划分为小问题进行解决，从而一步步获取最优解的解决算法。

动静布局算法与分治算法相似，其根本思维也是将待求解问题分解成若干个子问题，先求解子问题，而后从这些子问题的解失去原问题的解。与分治法不同的是，适宜于用动静布局求解的问题，经合成失去子问题往往 不是相互独立 的。动静布局算法对于下一个子阶段的求解，是建设在上一个子阶段的解的根底上进行进一步的求解。

动静布局和贪婪算法一样，是 求最优解 的一种思维办法，能够通过 填表 的形式来逐步推进，失去最优解。

为不便做题，可将动静布局不严格地分为四类：线性动静布局 、 二维动静布局 、 树形动静布局 、 背包问题。

牛客网动静布局专项将动静布局分成了九类：线性 dp、前缀和、差分、二维 dp、背包、区间 dp、树形 dp、状压 dp、数位 dp。

本文将介绍 线性动静布局 、 二维动静布局 、 背包问题 等三类。

1 线性动静布局

1.1 斐波那契数列问题

要求输出一个正整数 n，请你输入斐波那契数列的第 n 项。

本例见：牛客网 NC65 斐波那契数列

回顾经典的“斐波那契数列问题”，斐波那契数能够用两个初始条件和一个简略的递推式来定义：

$$
F(n)=
\begin{cases}
0, &n=0\\
1, &n=1\\
F(n-1) + F(n-2), &n>1
\end{cases}
$$

除了应用递归的办法求解，也能够应用非递归的办法。

对于 F(n) 的求解能够计算它的两个更小的交叠子问题 F(n-1) 和 F(n-2)，因而能够在一张 一维表 中填入 n+1 个 F(n) 的间断值：

代码如下：

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

动静布局算法能够解释为一种 空间换工夫的衡量技术。不过在“斐波那契数列问题”中，能够对动静布局再作改良，则可防止应用额定的空间，这里不赘述。

1.2 币值最大化问题

给定一排 n 个硬币，其面值均为正整数 C1, C2, …, Cn，这些整数并不一定两两不同。请问如何抉择硬币，使得在其原始地位互不相邻的条件下，所选硬币的总金额最大。

本例可参考：NC2 不相邻取数

如何抉择硬币呢？对于前 n 枚硬币的最大可选金额设为 F(n)。对于第 n 枚硬币（n≥2），事实上有两种状况：

  • 不抉择第 n 枚硬币，则前 n 枚硬币的最大可选金额与前 n-1 枚硬币的最大可选金额统一，即：F(n) = F(n-1)
  • 抉择第 n 枚硬币，则第 n-1 枚硬币肯定不可选，前 n 枚硬币的最大可选金额为第 n 枚再加上前 n-2 枚硬币：F(n) = Cn + F(n-2)

到底该抉择这两种状况的哪一种呢？两种状况取最大值即可。因而能够失去递推公式：

$$
F(n)=
\begin{cases}
0, &n=0\\
C_1, &n=1\\
max\{F(n-1),C_n + F(n-2) \}, &n>1
\end{cases}
$$

以一排硬币 {5, 1, 2, 10, 6, 2} 为例，填表过程如下：

前 6 枚硬币的最大可选金额即所求，故一排硬币 {5, 1, 2, 10, 6, 2} 的最大可选金额为 17。

建一维表时，如币值数组为 C[n]，则动静布局数组应为 F[n + 1]。

币值最大化问题的代码如下：

public class Solution {// 输出：数组 C[0..n-1]保留 n 个硬币的面值
    public int CoinRow(int[] C) {
        int n = C.length;
        if (n == 0) return 0;
        if (n == 1) return C[0];
        int[] F = new int[n + 1];
        F[0] = 0;
        F[1] = C[0];
        for (int i = 2; i <= n; i++) {F[i] = Math.max(F[i - 1], C[i - 1] + F[i - 2]);
        }
        return F[n];
    }
}

然而，以上填表过程仅仅得出最优解的值，并没有给出最优解的计划。要求出最优解抉择了哪些硬币，须要 回溯 上述计算过程。如何回溯呢？下文“01 背包问题”将作为列举回溯过程的例子，其思维是一样的。

1.3 不相邻取数问题

牛客网动静布局专题的 “不相邻取数问题” 与本例简直统一：

第一行输出一个正整数 n，代表数组长度。第二行输出 n 个正整数，代表整个数组。输入不相邻的数的最大和。

本例见：NC2 不相邻取数

这里贴一个我的解法：

import java.util.Scanner;

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long[] C = new long[(int) n];
        for (int i = 0; i < n; i++) {C[i] = sc.nextInt();}

        if (n == 0) {System.out.print(0);
            return;
        }
        if (n == 1) {System.out.print(C[0]);
            return;
        }
        long[] F = new long[(int) n + 1];
        F[0] = 0;
        F[1] = C[0];
        for (long i = 2; i <= n; i++) {F[(int) i] = Math.max(F[(int) i - 1], C[(int) i - 1] + F[(int) i - 2]);
        }
        System.out.print(F[(int) n]);
    }
}

1.4 找零问题

与 币值最大化问题 相似的，还有 找零问题：

需找零金额为 n，起码要用多少面值为 d1 < d2 < … < dn 的硬币？

这里贴个伪代码，不赘述：

2 二维动静布局问题

2.1 硬币收集问题

在 n×m 格木板中放有一些硬币，每格的硬币数目最多为一个。在木板左上方的一个机器人须要收集尽可能多的硬币并把它们带到右下方的单元格。每一步，机器人能够从以后的地位向右挪动一格或向下挪动一格。设计一个算法找出机器人能找到的最大硬币数。

本例可参考：NC9 字母收集

设第 i 行第 j 列的格子能收集的最大硬币数为 F(i , j)。如何达到第 i 行第 j 列这个格子呢？有以下两种状况：

  • 从上方单元格 (i-1 , j) 达到。
  • 从左方单元格 (i , j-1) 达到。

到底该抉择这两种状况的哪一种呢？两种状况取最大值即可。此外，还须要加上以后格子的硬币数 Cij。因而能够失去递推公式：

$$
F(i,j)=
\begin{cases}
0, & i=0, j=0 \\
0, & i=0, 1 \le j \le m\\
0, & j=0, 1 \le i \le n\\
max\{F(i-1,j),F(i,j-1) \} + C_{ij}, & 1 \le i \le n, 1 \le j \le m
\end{cases}
$$

以下图为例：

填表过程如下：

建二维表时，如硬币数组为 C[n][m]，则动静布局数组应为 F[n+1][m+1]。

先初始化第 0 行、第 0 列为 0，再依照递推公式填表即可。

填表时，既能够逐行填写，也能够逐列填写。为与以下代码保持一致，上图是逐行进行填写的。

所谓动静布局算法，即这个 填表过程的模仿：

public class Solution {public static void main(String[] args) {int[][] C = {{0, 0, 0, 0, 1, 0},
                     {0, 1, 0, 1, 0, 0},
                     {0, 0, 0, 1, 0, 1},
                     {0, 0, 1, 0, 0, 1},
                     {1, 0, 0, 0, 1, 0}};
        System.out.println("收集的最大硬币数为:" + coinCollection(C));
    }

    public static int coinCollection(int[][] C) {
        int n = C.length;
        int m = C[0].length;
        int[][] dp = new int[n + 1][m + 1];
        // 不须要初始化 dp 数组的第 0 行、第 0 列，因为 Java 的 int 数组默认值就是 0
        for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 图解中下标从 1 开始，代码中下标从 0 开始，故为 C[i-1][j-1]
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + C[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }
}

同样的，以上填表过程仅仅得出最优解的值，并没有给出最优解的门路。

2.2 字母收集问题

与本例相似的，还有牛客网动静布局专题的“字母收集问题”：

有一个 n×m 的矩形方阵，每个格子下面写了一个小写字母。小红站在矩形的左上角，她每次能够向右或者向下走，走到某个格子上就能够收集这个格子的字母。

小红十分喜爱 “love” 这四个字母。她拿到一个 l 字母能够得 4 分，拿到一个 o 字母能够得 3 分，拿到一个 v 字母能够得 2 分，拿到一个 e 字母能够得 1 分。
她想晓得，在最优的抉择一条门路的状况下，她最多能获取多少分？

本例见：NC9 字母收集

这里贴一个我的解法：

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] C = new char[n][m];
        for (int i = 0; i < n; i++) {String s = sc.next();
            for (int j = 0; j < m; j++) {C[i][j] = s.charAt(j);
            }
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + score(C[i - 1][j - 1]);
            }
        }
        System.out.print(dp[n][m]);
    }

    public static int score(char ch) {if (ch == 'l') return 4;
        else if (ch == 'o') return 3;
        else if (ch == 'v') return 2;
        else if (ch == 'e') return 1;
        else return 0;
    }
}

3 背包问题

因为篇幅无限，背包问题请看这里：【Java 算法系列】背包问题
（这篇背包问题强烈建议浏览！）

参考资料

  1. 尚硅谷：Java 数据结构与算法
  2. 分治算法详解及经典例题
退出移动版