动态规划 | Wang Yiran

介绍

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20 世纪 50 年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。(来自百度百科)

简单来说，就是把问题分成多个阶段，每个阶段都符合一个式子（状态转移），后面阶段的状态（结果）一般可以由前面阶段的状态（结果）转移而来。

找出状态转移方程，动态规划已经成功了 90%。使用动态规划求解时，最关键的是找出状态转移方程，而想要找出状态转移方程，首先要对问题状态有清晰的定义。一般来说，动态规划求解主要包括以下步骤：

划分阶段：把问题划分成子问题，类似于分治法，每个阶段一般是有序的。
定义状态：每个阶段，都有属于自己的最优状态，每一个阶段的最优状态，可以从前面阶段的最优状态中转化获得。
状态转化：不同阶段之间的转化关系，就是状态转移方程，定义好它们之间的递推关系，就是极其重要的一步。
逆向求解：一般来说我们要求解一个状态，需要先把前面的状态先求解。那么逆向就是自底向上，也就是先挨个把前面的状态求解，再使用前面的状态求解后面的状态。（注意最初的状态定义必须准确，边界值需要处理好）

动态规划一般是用来求解最优解的，这类问题一般有很多种解，但是我们期望的是找出其中的一个最优解。动态规划的厉害之处，在于分解大的问题，并且找出了递推的式子，能够利用前面的状态不断求解出后面的状态。

零钱兑换

问题描述

给定不同面额的硬币 coins 和一个总金额 amount，需要你编写一个函数计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，则返回 -1。你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5]，amount = 11

输出：3

解释：11 元可以拆分为 5 + 5 + 1，这是最少的硬币数目。

求解思路

利用 DP 求解问题时，不要一开始就去想第一步具体做什么！那么应该从哪里着手呢？答案是：最后一步！

兑换硬币的时候，假设每一步操作总是选择一个硬币，那么我们看一下最后一步如何达到 amount？

以给定的输入为例：

coins = [1, 2, 5], amount = 11

最后一步可以通过以下 3 个选项得到：

已经用硬币兑换好了 10 元，再添加 1 个 1 元的硬币，凑成 11 元；

已经用硬币兑换好了 9 元，再添加 1 个 2 元的硬币，凑成 11 元；

已经用硬币兑换好了 6 元，再添加 1 个 5 元的硬币，凑成 11 元。

接下来，应该立即将以上 3 个选项中的未知项展开成子问题！

子问题

拿到 3 个选项之后，你可能会想：[10元，9元，6元] 是如何得到？到此时，一定不要尝试递归地去求解 10 元、9 元、6 元，正确的做法是将它们表达为 3 个子问题：

如何利用最少的硬币组成 10 元？

如何利用最少的硬币组成 9 元？

如何利用最少的硬币组成 6 元？

我们原来的问题是，如何用最少的硬币组成 11 元。

不难发现，如果用 f(x) 表示如何利用最少的硬币组成 x 元，就可以用 f(x) 将原问题与 3 个子问题统一起来，得到如下内容：

原问题表达为 f(11)；

3 个子问题分别表达为 f(10)、f(9)、f(6)。

接下来我们再利用 f(x) 表示最后一步的 3 个选项：

f(10) + 1 个 1 元得到 f(11)；

f(9) + 1 个 2 元得到 f(11)；

f(6) + 1 个 5 元得到 f(11)。

递推关系

最后一步，可以通过 3 个选项得到。哪一个选项才是最少的步骤呢？这个时候，我们可以采用一个 min 函数来从这 3 个选项中得到最小值。

f(11) = min(f(11-1), f(11-2), f(11-5)) + 1

接下来，第一次替换：只需要将 11 换成一个更普通的值，就可以得到更加通用的递推关系：

f(x) = min(f(x-1), f(x-2), f(x-5)) + 1

当然，这里 [1, 2, 5] 我们依然使用的是输入示例，进行第二次替换：

f(x) = min(f(x-y), y in coins) + 1

代码实现

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
 var coinChange = function(coins, amount) {
    const f=[]
    f[0]=0
    for(let i=1;i<=amount;i++){
        f[i]=Infinity
        for(let j=0;j<coins.length;j++){
            if(i-coins[j]>=0){
                f[i]=Math.min(f[i],f[i-coins[j]]+1)
            }
        }
    }
    if(f[amount]===Infinity){
        return -1
    }
    return f[amount]
};

分割等和子集

问题描述

一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 1）每个数组中的元素不会超过 100；2）数组的大小不会超过 200

输入：A = [2, 2]

输出：true

解释：可以将这个数组分成 [2], [2] 这两个子集和是相等的。

求解思路

由于分出来的两个子集和要求是相等的，如果整个数组和为奇数，那么没有讨论的必要。这里我们只讨论 sum(A) = 2 x V 的情况。也就是分出来的两个子集，其和分别为 V。

这个问题，也可以想象成：

有一个容量为 V 的背包，给你一些石头，石头的大小放在数组 A[] 中，现在需要捡一些石头，刚好装满容量为 V 的背包。（你可以不去考虑填充的时候的缝隙）

代码实现

var canPartition=function(nums){
    let sum=0
    let len=nums.length
    for(let i=0;i<len;i++){
         sum+=nums[i]
    }
    if(sum%2!==0){
         return false
     }
     let target=sum/2
     //状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
     const dp= new Array(len).fill(0).map(() => new Array(target+1).fill(false))
     if (nums[0] <= target) {
        dp[0][nums[0]] = true;
    }
    for(let i=1;i<len;i++){
        for(let j=0;j<=target;j++){
            dp[i][j]=dp[i-1][j]
            if(nums[i]==j){
                dp[i][j]=true
                continue
            }
            if(nums[i]<j){
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
            }
        }
    }
    return dp[len - 1][target];

}