动态规划

摘要

本文主要介绍动态规划算法。通过斐波拉契数列和最长子序列两个案例介绍。对于一个非计算机相关专业的来说,笔者也是一边学习,一边整理学习文档,希望能帮到像笔者一样的初学者。

斐波拉契数列

先来看一个非常简单的例子,斐波拉契数列[1]前面有文章介绍过。但那篇文章并没有比较递归的耗时,因为递归存在重复计算问题,所以耗时会相当的长。

在使用动态规划时,也存在三种不同的算法:
1. 递归实现;存在重复计算,一般使用这种方法寻找递推关系(也称为状态转移方程)
2. 自顶向下的递归实现,但保存中间值。以空间换取时间,减少重复计算。
3. 自底向上递推式。

斐波拉契数列每一个值称为一个状态,状态转移方程为:

F(n) = F(n-1) + F(n-2), n \ge 3

边界条件为:

F(1) = 1, F(2)=1

问题可以重新描述为:任何一个状态的值都等于前两个状态之和。解决这个问题存在三种解法,第一种已经在斐波拉契数列中介绍过了,第三种自底向上递推的法就是循环法或者生成器法。第二种递归法,其实就是保留了就算结果中间值,这部分读者可以自行实现。

最长子序列问题

对于一个序列a_1a_2\cdots a_k\cdots a_n,如果存在a_{j1} < a_{j2} < \cdots < a_{jk} 其中 j1,j2,\cdots, jk \in (1, 2, \cdots, n), 并且依次递增,我们称这个序列是长度为k的一个子序列,如果这个序列是最长的,则成为最长子序列。

显然一个序列存在多个最长子序列,长度是相等的,因此我们只要找到最长子序列的长度,而无需输出这个序列。这个问题就是典型的动态规划问题。

求解问题的思路就是定义子问题,找到状态转移方程。子问题定义如下:
F(k)是以a_k结尾的最长子序列长度,那么如何寻找F(k)F(k-1)之间的关系呢?很明显它们之间并不存在直接关系。也就是无法建立类似斐波拉契数列那样直接的递推关系。但F(k)a_k以前(不包括a_k)的最长子序列F(i)有关,于是得到状态转移方程[2]为:

F(k) = \max_{1\le i< k} F(i)+ 1, if \quad a_i < a_k

直接使用自底向上的递推式,使用Java编程,由于本人最近开始学习Java,有空会整理更多的Java笔记。

package learn;

/**
 * @function:动态规划求解最长上升子序列
 * @author:Vincent
 */
public class MaxSubSequence {

    public static void main(String[] args) {

        int a[] = { 1, 3, 7, 5, 8, 10, 9, 2 };
        System.out.println(subSequence(a, 5));

    }

    private static int subSequence(int a[], int N) {
        if (N >= a.length)
            return -1;

        int size = N + 1;

        int[] maxLen = new int[size];

        for (int i = 0; i < size; i++)
            maxLen[i] = 1;

        for (int i = 1; i < size; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i])
                    // 不断更新第i个值的子序列数
                    maxLen[i] = max(maxLen[i], maxLen[j] + 1);
            }
        }
        return maxLen[N];
    }

    private static int max(int i, int j) {
        return i > j ? i : j;
    }

}

参考资料

关注机器学习和算法的码农,喜欢编程和读书
文章已创建 74

发表评论

电子邮件地址不会被公开。

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部