乐趣区

关于前端:算法题动态规划

动静布局(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。

动静布局的核心思想:下一个状态能够由上一个状态推导而来,因而能够 利用数组保留之前计算的后果,防止反复计算

咱们来看一个经典案例:斐波那契数列

function fibonacci(n) {if(n == 0 || n == 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2)
}

下面的代码看似简略,但其实存在一个重大问题。通过下图咱们能够看出,在递归过程中,很多节点被反复计算了,这些无疑导致了性能损失,而且随着问题规模的变大,反复计算的节点呈几何级数增长。

那么怎么样优化这个流程呢?由斐波那契数列的个性能够看出,第 n 个节点的值能够由第 n-1 和第 n-2 个节点推导进去,合乎动静布局的逻辑,因而咱们能够用一个数组保留之前的状态,防止反复计算。

function fibonacci(n) {if (n == 0 || n == 1) return n; // 边界值解决
    let dp = new Array(n);
    dp[0] = 0; // 初始条件
    dp[1] = 1;
    for (let i=2; i<n; i++) {dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
    }
    return dp[n-1]
}

下面的代码中,咱们用了一个长度为 n 数组保留之前的状态,工夫复杂度升高到了 O(n),极大进步了效率。从下面的代码中,咱们能够总结出动静布局的两个外围组成部分:初始条件和边界状况 以及 状态转移方程。所谓状态转移方程,也就是由上一个状态推导到下一个状态的递推公式。在下面的例子中,状态专转移方程能够形象为:

f(i) = f(i-1) + f(i-2)

一般来说,求第 n 个元素,须要开一个长度为 n 的数组,空间复杂度为 O(n)。然而在斐波那契数列的例子中,咱们只关怀以后状态的前两个状态就行,不须要把之前所有的状态都给保留下来。因而,下面的代码还能够再优化,只创立一个长度为 2 的数组就满足需要了,空间复杂度降为常数阶。

function fibonacci(n) {if (n == 0 || n == 1) return n;
    let dp = [0, 1];
    for (let i=2; i<n; i++) {let res = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = res % 1000000007;
    }
    return dp[1];
}

剑指 Offer 42 间断子数组的最大和

class Solution {public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int max = nums[0];

        for (int i=1; i<len; i++) {dp[i] = Math.max((dp[i-1] + nums[i]), nums[i]);
            max = Math.max(dp[i], max);
        }

        return max;
    }
}

leetcode 64 最小门路和

leetcode 300 最长递增子序列

参考:

肝了好多天 - 动静布局十连 - 超细腻解析|刷题打卡

动静布局 – 小彭的博客

退出移动版