A Quick Note of Dynamic Programming and Greedy Algorithm
Greedy Algorithm
-
For the greedy algorithm, it basically looks at whether it is an extreme value problem, and generally goes through the local optimal solution and finally derives the global optimal solution. However, the local optimal solution of the greedy algorithm has no posteriority.
-
The first thing you need to ** confirm the whole idea of the problem ** is how to derive the global optimal solution through the local solution.
-
Next is the implementation, which is generally done in iterations to find the local optimal solution; then iterations are derived based on the previous ideas to achieve the derivation of the optimal solution.
Dynamic programming
-
For dynamic programming is also generally an extreme value problem, also involving optimal sub-structures, but the difference is that dynamic programming also involves overlapping sub-problems (that is, sub-problems are generally not independent)
-
By independent, I mean that I calculate the solution to this subproblem and that's it. The next subproblem follows the same algorithm, but is not related to the solution of the previous subproblem. Not independent, like dynamic programming problems in general the solution of the current subproblem may be based on the solution of some previous subproblem. This is related to the problem of dynamic programming itself. After the problem is decomposed, it is found that there are many repeated calculations, and in order to reduce these redundant calculations, memorization and dynamic programming are used to optimize the idea.
Differences
-
Both greedy and dynamic programming have the nature of optimal substructure, i.e., the global optimal solution contains the optimal solution of the subproblem.
-
The difference is that dynamic programming has overlapping subproblems, whereas the greedy algorithm does not. In addition, dynamic programming is a bottom-up decomposition problem, and greedy is not quite similar (somewhat top-down).
Give a gnawing example
Problem
- Coin Change
You have several denominations of coins to use as you wish, and a number of coins, pick the fewest coins to make up that number.
Algorithm
When I first started working on this problem, I naturally chose the greedy algorithm. The idea is to pick the largest denomination until the number of coins left is not enough for the largest denomination, and then pick the second largest, and so on until the composition or group can not be the number of money.
After the interviewer tips found a kind of case can not pass, the code accordingly do not know how to change.
Where does the problem lie here?
Overlapping sub-problems. The basis of greed is not dependent on the overlapping subproblems, if the subproblems overlap, greed can not come up with the true extreme value (optimal solution). This topic has an overlapping subproblem (that is, the greedy idea to go to the end of the non-optimal solution, you need to go back one step to find again.)
This topic we now consider with the idea of dynamic programming. From the bottom up, several aspects.
The state, that is, according to the result, our state dp[i] is the minimum number of coins needed when the number of money is i.
Transfer formula: dp[i] = min(dp[i - coin[k]], dp[i]);, there are several choices, i.e. different denominations of coin.
Initialization: when the money to be composed is 0, no coin, so also dp[0]=0.
Code
import java.util.Arrays;
/**
* Created by szhang on 2023/3/22
*/
public class CoinChange {
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] coins = new int[]{5, 2, 1};
System.out.println(coinChange(coins, 0)); // 0
System.out.println(coinChange(coins, 5)); // 1
System.out.println(coinChange(coins, 10)); // 2
System.out.println(coinChange(coins, 11)); // 3
System.out.println(coinChange(coins, 12)); // 3
}
}
贪心算法
-
对于贪心算法，基本上是看一下是否是极值问题，一般都是通过局部最优解，最后推导全局最优解。不过贪心算法的局部最优解没有后效性。
-
首先需要确认整个问题的思路，就是如何通过局部解推导出全局最优解。
-
其次是实现了，一般是在迭代中求出局部最优解；然后迭代根据之前的思路推导，实现推导出最优解。
动态规划
-
对于动态规划来说一般也是极值问题，也涉及到最优子结构，但是区别在于，动态规划还涉及到重叠子问题（也就是子问题一般不是独立的）
-
所谓独立是说，我算出这个子问题的解就到这，下一个子问题按照同样的算法去算，但是和前一个子问题的解无关联。不独立，像动态规划问题一般当前的子问题的解可能是基于之前的某个子问题的解。为什么会出现这个情况呢，这个和动态规划问题的问题本身有关，问题经过分解之后会发现存在诸多重复的计算，为了减少这些冗余的计算才出现了记忆化memorization和动态规划来优化思路。
区别
-
贪心和动态规划都具有最优子结构性质，即全局的最优解包含子问题的最优解。
-
区别在于动态规划是还有重叠子问题，而贪心算法不是。另外动态规划是自底向上的分解问题，贪心的思路也不太类似（有点自顶向下）。
举一个耿耿于怀的例子
问题
322.Coin Change
你有几种面值的硬币可以随便用，还有一个钱数，挑选最少的硬币组成这个钱数。
算法
这个题目在我刚开始做题的时候，自然而然的就选择了贪心算法。比较natrually的想法就是先挑面值最大的，直到剩下的钱数不够一个面值最大的，再挑第二大的，依次循环直到组成或者组不成这个钱数。
后面经过面试官提示发现有种case过不了，代码相应的也不知道怎么改。
这里的问题出在哪里呢？
重叠子问题。贪心的基础是不依赖重叠子问题的，如果子问题重叠，贪心也不能得出真正的极值（最优解）。这个题目出现了重叠的子问题（就是说按照贪心的思路走到最后非最优解，需要往前退一步再找。）
这个题目我们现在用动态规划的思想去考虑。自底向上，几个方面：
状态，就是根据结果，我们的状态dp[i]就是当钱数为i的时候需要的最少硬币数量；
转移公式：dp[i] = min(dp[i - coin[k]], dp[i]);，选择有几种，即不同的coin的面值；
初始化：当需要组成的钱为0的时候，不要硬币，所以也是dp[0]=0。
代码
import java.util.Arrays;
/**
* Created by szhang on 2023/3/22
*/
public class CoinChange {
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] coins = new int[]{5, 2, 1};
System.out.println(coinChange(coins, 0)); // 0
System.out.println(coinChange(coins, 5)); // 1
System.out.println(coinChange(coins, 10)); // 2
System.out.println(coinChange(coins, 11)); // 3
System.out.println(coinChange(coins, 12)); // 3
}
}