leetcode–两个子序列的最大点积–动态规划

一、什么是动态规划

假设你现在呆在A处，目标去G处。如果问你有几种走法，那你会很快算出答案。但现在告诉你每条路上花费时间是不同的，问你如何找到一条最快的路线？你可能会说这也简单，把每一条路线的时间都算出来，然后对比就可以得出。

但学过运筹学还要运用暴力破解法是可耻的行为。我们需要分多阶段进行决策。
这类问题就是动态规划问题，下面介绍动态规划的基本概念与符号。

基本定义

我们可以将每次决策分为一个阶段，上例就可以分为A——G阶段，在每个阶段都有不同的选择，我们将这些选择称为状态，如点集{B1,B2}为第二阶段的可达状态集合。

状态需要满足的一个特性是：当阶段状态给定后，以后的发展不受此阶段之前各段的影响（跟人生不一样），这一种性质称为无后效性。

在每一阶段你可以做出不同的选择，这种选择叫做决策。由决策按顺序组成的集合叫做策略。由第k阶段到到终止阶段为止的过程，称为k子过程。在实际中，可供选择的策略是有限的，这有限的集合叫允许策略集合。

所以在允许策略集合里找到最优策略。
假如我们知道了一个规划问题当前的状态和决策变量，那我们可以立即确定下一个状态。记k阶段的状态变量为 S(k) 决策变量为 p(k + 1)。状态转移方程为 T : S(k+1) = opt {S(k), p(k + 1)} ,其中T称为状态转移函数。
我们还需要一个函数来评价所选策略的优劣，我们称之为指标函数，指标函数可以用来衡量一个一个决策的优劣。

最优性原理：最优策略的子策略也一定是最优的。

二、利用动态规划思想解决程序问题

2.1、 状态方程

我们用二维数组的变量 f[ i ][ j ] 来表示状态，表示 nums1 数组的前 i 个元素和 nums2 的前 j 个元素，所组成的子序列的最大点积，这里的元素下标从 0 开始。

2.2、状态转移函数

那么如何进行状态转移呢？我们可以考虑每个数组中的最后一个元素：

如果我们选择了nums1数组的第 i 个元素和nums2数组的第 j 个元素，并将它们形成点积，那么这一对数字对答案的贡献为 xij = nums[ i ] * nums[ j ] 。在选择了这一对数字之后，前面还有 nums 1 的前 i-1 个元素以及数组 nums2 的前 j – 1 个元素，我们可以在其中选择数字对，也可以不选择，因为题目描述中唯一的限制就是选择的子序列非空，而我们已经选择了 xij 。

如果我们在前面的元素中选择数字对，那么最大点积即为 f[i-1][j-1] + xij;

如果我们不选择前面的数字对，那么最大点积即为 xij;

如果我们没有选择 nums1[ i ] 以及 nums2[ j ] 形成点积，由于它们是各自子序列的最后一个元素，因此其中至少有一个不会与其它的任意元素形成点积。

这样我们可以扔掉nums1[ i ] 和 nums2[ j ] 中的至少一个元素：

如果扔掉 nums1[ i ]，那么最大点积即为 f[i − 1][ j ]；

如果扔掉 nums2[ j ]，那么最大点积即为 f[ i ][j − 1]；

如果同时扔掉 nums1[ i ] 和 nums2[ j ]，那么最大点积即为 f[i − 1][j − 1]。

根据上面的分析，我们就可以写出状态转移方程；

f[ i ][ j ] = max( f[i – 1][j – 1] + xij, f[i – 1][ j ], f[ i ][j – 1], f[i – 1][j – 1], xij)

注意到状态转移方程中有一个可以优化的地方，这是因为 f[i − 1][ j ] 以及 f[ i ][j − 1] 对应的状态转移方程中已经包含了 f[i − 1][j − 1]，因此可以从状态转移方程中移除这一项，即：

f[ i ][ j ] = max( f[i – 1][j – 1] + xij, xij, f[i – 1][ j ], f[ i ][j – 1] )

动态规划的边界条件也非常容易处理。在对 f[ i ][ j ] 进行转移时，我们只要处理那些没有超出边界的项就行了。最后的答案即为 f[m − 1][n − 1]，其中 m 和 n 分别是数组 nums 1以及数组 nums 2的长度。

附录：代码

public int maxDotProduct(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int[][] f = new int[m][n];

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int xij = nums1[i] * nums2[j];
            f[i][j] = xij;
            if (i > 0) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j]);
            }
            if (j > 0) {
                f[i][j] = Math.max(f[i][j], f[i][j - 1]);
            }
            if (i > 0 && j > 0) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + xij);
            }
        }
    }

    return f[m - 1][n - 1];
}
复制代码