动态规划算法
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出**正确的「状态转移方程」**才能正确地穷举。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
# 一、斐波那契数列
image-20200809215908467
package com.zhanbo.dynamicplanning;
/**
* @author ZhanBo
* @date 2020/8/9
*/
public class Fibonacci {
int fib(int N) {
int [] dp = new int[N+1];
// base case
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
/**
* 压缩dp数组，因为dp的状态只与前两个状态有关。
* @param n
* @return
*/
int fib2(int n) {
if (n == 2 || n == 1) {
return 1;
}
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
}# 二、凑零钱问题
先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下
package com.zhanbo.dynamicplanning;
import java.util.Arrays;
/**
* @author ZhanBo
* @date 2020/8/9
*/
public class CollectChange {
static int coinChange(int[] coins, int amount) {
// 数组大小为 amount + 1，初始值也为 amount + 1
int[] dp = new int[amount+1];
Arrays.fill(dp,amount+1);
// base case
dp[0] = 0;
// 外层 for 循环在遍历所有状态的所有取值
for (int i = 0; i < dp.length; i++) {
// 内层 for 循环在求所有选择的最小值
for (int coin : coins) {
// 子问题无解，跳过
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
public static void main(String[] args) {
System.out.println(coinChange(new int[]{3, 100, 10}, 11));
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录