2.3 动态规划算法

2.3.1 什么是动态规划算法

动态规划算法是一种常用的问题解决方法。它通过将问题分解为更小的子问题，并保存子问题的解，以避免重复计算。与分治法不同的是，动态规划算法的子问题往往是不相同的且有关联的。

动态规划的核心在于：

• 现在的问题由过去求解，分析当前解是如何从过去的解中得到的，即从问题中得到递推式。

• 使用一个表来记录所有已解决的子问题的答案，不管他以后是否被用到，只要他被计算过，就将其结果记录表中。

• 明确dp[i][j]所指的含义

这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.3.2 动态规划的适用场景

动态规划适用于：

• 问题可以被分解为更小的子问题进行求解的场景

一些常见的应用场景包括：

• 背包问题： 给定一组物品和一个背包，每个物品有自己的重量和价值，要求选择一些物品放入背包，使得背包中物品的总价值最大。动态规划算法可以帮助我们解决这个问题，通过构建一个价值表格，在每个状态下选择最优的决策。

• 最长公共子序列问题： 给定两个字符串，找到它们之间最长的共同子序列的长度。通过构建一个二维表格，依次计算每个子问题的最长公共子序列长度，并保存在表格中。

• 最优路径规划： 在一个网格中，从起点到终点，要求找到路径的总和最小或者最大的路径。动态规划算法可以通过构建一个二维表格，依次计算每个子问题的解，并保存在表格中，最终得到最优路径。

2.3.3 动态规划模板

// 对于递推式f(n) = f(n-1) + f(n-2)
void func(int[] nums) {
	int[] dp = new int[nums.length];
	dp[0] = 0; // 边界条件
	dp[1] = 1; // 边界条件
	for (int i=3; i< dp.length; i++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[nums.length-1];
}

2.3.4 动态规划详解

2.3.4.1 leetcode 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[100,2,3,100]
输出：200
解释：偷窃 1 号房屋 (金额 = 100) ，然后偷窃 4 号房屋 (金额 = 100)。
     偷窃到的最高金额 = 100 + 100 = 200 。

分析：

• 递推式 ： dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1])，即相邻的金币比较大，则不偷取当前的房屋，若相隔一间加上当前房屋的数额比相邻的大，则偷取当前房屋，并计算能偷取的最大值。
• dp[i]为当前能偷盗金币的最大值。

2.3.4.1 背包问题

2.3.4.2 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

分析：

以nums[i]为最长递增子序列的结尾，dp[i]为以nums[i]为最长递增子序列的结尾的序列最大长度。 当遍历到nums[i]时，其最长递增子序列可以由上一个小于他的数的最长递增子序列的最大值得到，则得到递推式dp[i] = preMax + 1; 如何得到上一个小于他的数的最长递增子序列的最大值呢，则需要再遍历一遍dp[]因此还需要一个for循环来遍历dp[]。 代码如下：

// 动态规划解法
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n  = nums.length;
        if (n == 1) return 1;
        int[] dp  = new int[n];
        dp[0] = 1;
        int res = 1;
        for (int i = 1;  i<n ; i++) {
            int tempMax = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j]< nums[i] && dp[j] > tempMax) {
                    tempMax = dp[j];
                }
            }
            dp[i] = tempMax + 1;
            if (dp[i] > res) res = dp[i];
        }
        return res;
    }
}