动态规划 Dynamic programming

[yijinc]

动态规划（Dynamic programming，DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于普通解法。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性。动态规划只解决每个子问题一次，并把子问题结果保存起来，以减少重复计算，再利用子问题结果依次计算出需要解决的子问题，直到得出原问题的解。

常用解题思路：

• 1、理解题意，找规律，定义 dp[i]
• 2、找出 dp[i]与前面计算得出的 dp[i-1]、dp[i-2]...的关系，转化成（条件）方程

练习题

• leetcode 53. 最大子数组和
• leetcode 70. 爬楼梯
• leetcode 62. 不同路径
• leetcode 63. 不同路径 II
• leetcode 64. 最小路径和
• leetcode 118. 杨辉三角
• leetcode 121. 买卖股票的最佳时机
• leetcode 122. 买卖股票的最佳时机 II
• leetcode 5. 最长回文子串
• leetcode 42. 接雨水

/**
* [leetcode 53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)
* dp[i] 表示 第i个元素位置往前的 最大和
***/
function maxSubArray(nums: number[]): number {
    const len = nums.length;
    const dp = new Array(len).fill(0);
    dp[0] = nums[0];
    for (let i = 1; i < len; i++) {
        if (dp[ i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i];
        } else {
            dp[i] = nums[i];
        }
    }
    return Math.max(...dp);
};