思路 这题是完全背包问题，关于背包问题，可以阅读这篇文章。https://huadonghu.com/archives/cn/dp2/ 对于0 <= i <= n，以及x1,x2,…xn种面值的硬币，T(i) = T(i-xi) 这一题的详细解释可以参考这篇博文：https://huadonghu.com/archives/en/dpv-6-17-coins-of-denominations/ 参考代码
[Leetcode]518. Coin Change 2
Posted on
DPV 6.19 Solution: Coin change with at most k uses of each coin
Posted on
Problem Description Solution Subproblem: For any integers 0 ≤ u ≤ v and 0 ≤ j ≤ k, define T(u, j) to be true if it is possible to make change for u using at most j coins with denominations chosen from x1, x2, . . . , xn. The answer we want is T(v,…
DPV 6.18 Solution: Coin change with at most 1 use of each coin
Posted on
Problem Description Solution Subproblem: To make change for u with denominations 1 through i, we have the choice of using a denomination i coin or not. If we use this coin, then we have to make change for u−xi using denominations 1 through i−1. If we don’t use this coin, then we have to make…
DPV 6.17 Solution: Coins of Denominations (Coin Changes)
Posted on
Problem Description Solution Subproblem: For any integer 0 ≤ i= ≤ k, define T(i) to denote if it is possible to make change for i using coins of denominations x1, x2, . . . , xn, thus the answer T(v). Recursive formulation: Notice that T(i) is true only if T(i – xi) is true for…
[Leetcode]312. Burst Balloons 爆破气球
Posted on
思路 这一题，其实是矩阵链乘法的变形题，关于矩阵链乘法，可以阅读这篇博文https://huadonghu.com/archives/cn/dp2/。 参考代码
Prove that High-Degree Independent Set is NP-Complete
Posted on
Problem In the High-Degree Independent Set (HDIS) problem, you are given a graph G = (V, E) and an integer k, and you want to know whether there exists an independent set V’ in G of size k such that each vertex of V’ is of degree at least k. (For example, the graph in…
[DPV]8.15 MAXIMUM COMMON SUBGRAPH
Posted on
Problem Show that the following problem is NP-complete.MAXIMUM COMMON SUBGRAPH Solution First, we need to prove that MAXIMUM COMMON SUBGRAPH (MCSP) is in the class NP. For given solution V1′ and V2′ , we simply remove these sets of vertices and their incident edges from G1 and G2 and check where the left G1′ and…
[DPV]8.2 Search versus decision.
Posted on
Language 中文版请访问：https://huadonghu.com/archives/cn/dpv8-2-search-versus-decision/ Problem Description Search versus decision. Suppose you have a procedure which runs in polynomial time and tells you whether or not a graph has a Rudrata path. Show that you can use it to develop a polynomial time algorithm for RUDRATA PATH (which returns the actual path, if it exists). Solution Let Ad…
[Leetcode] 969. Pancake Sorting 烙饼排序
Posted on
Solution Code 聊一聊NP-Hard
[DPV]8.3 STINGY SAT
Posted on
Language For English Version, please visit: https://huadonghu.com/archives/en/algorithms/dpv8-3-stingy-sat-2/ Problem Description STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY SAT is NP-complete. STINGY SAT 是：对于对于一组cluses和一个正整数k，…