<h1>常见的动态规划问题(二）</h1>
<p>本文转载于GitHub地址：<a href="https://github.com/CyC2018/CS-Notes/">https://github.com/CyC2018/CS-Notes/</a>，仅作为个人日后复习。整合了多方面的资料，侵删。</p>
<h2>引例解析：</h2>
<p>内容来源于公众号文章：<a href="https://mp.weixin.qq.com/s/lKQI0aS1MBwfPujC-m_zkA">https://mp.weixin.qq.com/s/lKQI0aS1MBwfPujC-m_zkA</a></p>
<p><img alt="" height="789" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-cfc6694345cc9cae1ff3dac8c2d5ebef.png" width="695"></p>
<p><strong>运用动态规划四部曲来进行解答：</strong></p>
<p><img alt="" height="921" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-630f1cb527fffac2d6432bb415d6d85f.png" width="675"></p>
<p><img alt="" height="268" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-65a6fb538785cde7851c9ef165d5f178.png" width="675"></p>
<pre class="blockcode"><code class="language-java">//解法一
public int coinChange(int[] coins, int amount) {
// 子问题：
// f(k) = 凑出金额 k 的最小硬币数
// f(k) = min{ 1 + f(k - c) }
// f(0) = 0
int[] dp = new int[amount+1];
Arrays.fill(dp, amount + 1); // DP 数组初始化为正无穷大
dp[0] = 0;
for (int k = 1; k <= amount; k++) {
for (int c : coins) {
if (k >= c) {
dp[k] = Math.min(dp[k], 1 + dp[k-c]);
}
}
}
// 如果 dp[amount] > amount，认为是无效元素。
if (dp[amount] > amount) {
return -1;
} else {
return dp[amount];
}
}
//解法二
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
for (int coin : coins) {
for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
if (i == coin) {
dp[i] = 1;
} else if (dp[i] == 0 && dp[i - coin] != 0) {
dp[i] = dp[i - coin] + 1;
} else if (dp[i - coin] != 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}</code></pre>
<p>这道题进行空间优化很麻烦，所以我们忽略第四步空间优化的步骤。</p>
<p><img alt="" height="927" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-76e363dde9b77c82747c0c0e128f61af.png" width="698"></p>
<p><img alt="" height="786" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-cfa31d6761291e59b59619b0523b440d.png" width="688"></p>
<pre class="blockcode"><code class="language-java">public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1]; // 默认初始化为 0
dp[0] = 1; // 注意 base case
for (int k = 1; k <= target; k++) {
for (int n : nums) {
if (k >= n) {
dp[k] += dp[k-n];
}
}
}
return dp[target];
}</code></pre>
<p><img alt="" height="910" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-f9bfd5f195f2c8f3b0ae6db9f9afad91.png" width="689"></p>
<p><img alt="" height="905" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-4322cd42e77f02d22e9f69ede41faec5.png" width="687"></p>
<p><img alt="" height="934" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-0c0418154f37c4d4bbb20ca1a90fd3ad.png" width="711"></p>
<pre class="blockcode"><code class="language-java">//解法一
public int change(int amount, int[] coins) {
int m = coins.length;
int[][] dp = new int[m+1][amount+1];
for (int i = 0; i <= m; i++) {
for (int k = 0; k <= amount; k++) {
if (k == 0) {
dp[i][k] = 1; // base case
} else if (i == 0) {
dp[i][k] = 0; // base case
} else {
dp[i][k] = dp[i-1][k];
if (k >= coins[i-1]) {
dp[i][k] += dp[i][k-coins[i-1]];
}
}
}
}
return dp[m][amount];
}
//解法二
public int change(int amount, int[] coins) {
if (coins == null) {
return 0;
}
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}</code></pre>
<h2>1.0-1背包问题</h2>
<p>有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。</p>
<p>定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：</p>
<ul><li>第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。</li><li>第 i 件物品添加到背包中，d |
|
转播
