他们翻出了1977年的Apple II

如上图所示，我们想要求得dp[i][j]，需要知道dp|[i-1]|[j-1]和dp[i-1][j]的值。因为只有(i - 1, j - 1) 和 (i - 1, j) 这两个点，才能能走到 (i, j)此时的状态转移方程为

第一种状态转移方程dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + val[i][j]

第二册中状态转移方程dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + val[i][j]

从这里可以知道我们的状态定义不一样，我们的转移方程就很不一样吧

• 正确性证明

数学归纳法通常采用三步走的方式，常用的正确性证明方法为数学归纳法。

第一步，第一个阶段所有dp值可以轻松获得，也就是初始化dp[1][1]，等于val[1][1]

第二步，假设如果第i-1阶段的所有状态值都正确得到，那么根据状态方程dp[i][j]=max(dp[i - 1][j], dp[i - 1][j + 1]) + val[i][j] 来说，此时就可以计算得到第i阶段中的素有状态值

第三步：得出结论，所有的状态值计算正确

我们继续分析动态规划问题中的0/1背包问题，通常分为三类，0/1背包问题，完全背包问题和多重背包问题。

0/1背包问题是另外两种背包问题的基础，简单描述一下，假设有个背包，载重上限为W，此时有n个物品，第i个物品的重量是wi，价值为vi，那么在不超过背包重量上限的前提下，能获得的最大物品价值总和?同样我们采用四步走的方式

• 状态定义

首先分析背包问题中的自变量和因变量，其中因变量比较好确定，就是所求最大价值总和，自变量呢，在此自变量为物品种类和背包承重上限，因为这两者会影响价值总和的最大值，所以我们设置一个二维状态。dp[i][j]代表使用前i个物品，背包最大载重为j的情况下最大价值总和。

• 状态方程

说白了就是找映射函数，dp[i][j]的表达式。我们将dp[i][j]分为两大类，第一类是不选择第i个物品最大价值和，第二类为选择了第i个物品的最大价值和。然后在两者中选择最大值就是价值更大的方案。

如果选择第i个物品，此时的最大价值为dp[i-1][j-wi]+vi，既然选择了第i个商品，那么就需要留出一个位置，那么此时对于剩余的i-1个商品的载重空间就只剩下j-wi了，此时i-1个物品选择的最大价值和为dp[i-1][j-wi]，然后加上vi就是当前获得最大价值和。所以转移方程为

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

• 正确性证明

首先dp[0][j]=0，意味着没有物品的时候，无论背包限重多少，能够得到的最大价值和都是0，所以k0争取

其次，假设我们已经获取i-1个物品的价值最大值，所有dp[i-1]的值，那么根据状态方程，我们能知道所有dp[i]的值

最后两步联合，整个求解对于任意dp[i][j]成立

• 实现

 

（编辑：南通站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!