动态规划学习笔记

发表于 2023-03-19 更新于 2023-05-03 分类于学习笔记 Waline：

摘要：动态规划学习笔记

动态规划

通过把原问题分解成若干个子问题（所有这些问题在一定意义上答案固定），再利用已知的子问题答案依次计算未知问题的答案，最终得到原问题答案的方式，称之为动态规划（Dynamic Programming，简称 DP）。

动态规划利用若干条信息来标识一个状态，按照一定的顺序依次计算这些状态对应的答案，每一个状态的计算都利用上之前计算过的状态（类似递推的由已知得到未知），由此降低问题本身的复杂程度。

动态规划的状态可以笼统的解释为“问题所在的局面”。状态的定义是明确的，具有无后效性以及最优子结构性质。

用 $f_i$ 表示总金额为 $i$ 时最少用多少张纸币。

如果 $i-a_j \ge 0$ ，则可以先用 $f_{i-a_j}$ 张纸币凑齐 $i-a_j$ 元，再用一张 $a_j$ 元的纸币，即可凑齐 $i$ 元。

可以得到状态转移方程：

1	if(i-a[j]>=0) f[i]=min(f[i],f[i-a[j]]+1);

用 $f_i$ 表示总金额为 $i$ 时有多少种方式。

如果 $i-a_j \ge 0$ ，则有 $f_{i-a_j}$ 种方式凑齐 $i-a_j$ 元，再用一张 $a_j$ 元的纸币来凑齐 $i$ 元。

可以得到状态转移方程：

1
2
3

for(int i=1;i<=w;i++)
    for(int j=1;j<=n;j++)
        if(i-a[j]>=0) f[i]+=f[i-a[j]],f[i]%=mod;

与上一道题相似，但是要求硬币组合的数量。

对于上一道题，我们要保证 $f_{i-a_j}$ 是最终答案，因此我们先枚举 $i$ 再枚举 $j$ 。

但是这道题，我们要保证 $f_{i-a_j}$ 是由编号为 $1 \sim j-1$ 这几种纸币拼出来的方案数，不能有其它纸币参与。

因此我们先枚举 $j$ 再枚举 $i$ 即可。

1
2
3

for(int j=1;j<=n;j++)
    for(int i=1;i<=w;i++)
        if(i-a[j]>=0) f[i]+=f[i-a[j]],f[i]%=mod;

用 $f_{i,j}$ 记录到达点 $(i,j)$ 处的最大路径。

而点 $(i,j)$ 可能由 $(i-1,j)$ 或 $(i-1,j-1)$ 直接向下一步走到，于是推出转移方程：

dp[1][1]=a[1][1];
for(int i=1;i<=n;i++) 
    for(int j=1;j<=i;j++) 
        f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);

01 背包模板题。

假设 $v_i$ 为物体的体积， $c_i$ 为物体的价值。将这 $n$ 个物体放入一个体积为 $V$ 的背包中。

假设 $f_{i,j}$ 表示将前 $i$ 个物品放入容量为 $j$ 的背包中，最大价值是多少。

则有转移方程：

f_{i,j}=\left \{ \begin{array}{ll} \max\{f_{i-1,j-v_i}+c_i,f_{i-1,j}\} & (j\ge v_i)\\ f_{i-1,j} & otherwise \end{array} \right.

因为有两种选择：选或不选。

若选第 $i$ 个物体，则前 $i-1$ 个物体体积要小于 $j-w_i$ ，得出 $f_{i-1,j-v_i}+c_i$ 。若不选第 $i$ 个物体，则等价于只选前 $i-1$ 个物体，得出 $f_{i-1,j}$ 。

看转移方程。第一维都是 $i-1$ ，于是我们想办法将第一维消掉。

再看第二维，计算 $f_{i,j}$ 时，第二维的值都小于等于 $j$ 。要想将第一维消掉，则需要保证，在更新 $f_{i,j}$ 时， $f_{i,j-v_i}$ 没有被更新过。

于是我们可以省掉第一维，然后从大到小遍历 $j$ 。

1
2
3

for(int i=1;i<=n;i++)
    for(int j=V;k>=v[i];j--)
        f[j]=max(f[j],f[j-v[i]]+c[i]);

完全背包模板题。

与上一题相比，这一题每个物品都有无限个。

上一题倒着遍历，其实还为了保证，更新 $f_i$ 时， $f_{j-v_i}$ 没有将第 $i$ 个物品算进去。因为上一题每件物品只有一个。

而这道题每个物品有无数个，我们恰好要保证：更新 $f_i$ 时， $f_{j-v_i}$ 已经将第 $i$ 个物品算进去。

因此正着遍历即可。

1
2
3

for(int i=1;i<=n;i++)
    for(int j=v[i];k<=V;j++)
        f[j]=max(f[j],f[j-v[i]]+c[i]);

------待更新------