labuladong动态规划解题套路框架
动态规划之背包汇总
第零章：动态规划解题套路框架
第一章：经典动态规划：0-1 背包问题
第零章：经典动态规划：子集背包问题
第零章：经典动态规划：完全背包问题
动态规划一般采用自底向上的方式求最值。
求解动态规划的核心问题是穷举,但是穷举过程中会存在重叠子问题，所以加上备忘录来优化过程
dp 三要素：
- 明确 base case
- 明确「状态」-> 明确「选择」, 即状态转移方程
- 确定「状态」，也就是原问题和子问题中会变化的变量
- 确定「选择」，也就是导致「状态」产生变化的行为
- 明确 dp数组/函数的含义
因此，dp 框架可写成：
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)509. 斐波那契数
class Solution(object):
def fib(self, N):
"""
:type N: int
:rtype: int
"""
if N==0: return 0
dp=[0 for _ in range(N+1)]
dp[1]=1
for i in range(2,N+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[-1]//#include <iostream>
//#include <vector>
//using namespace std;
class Solution{
public:
int fib(int N){
if (N==0)
return 0;
vector<int> dp(N+1);
dp[1]=1;
for (int i = 2; i <N+1; i++) {
dp[i]=dp[i-1]+dp[i-2];
}
return dp[N];
}
};
//int main(){
// int s=Solution().fib(5);
// cout<<s<<endl;
//}
322. 零钱兑换
方法1：二维dp数组
dp[i][j]的含义：前i枚硬币凑成j块钱所需要的最小硬币数
- 因为求最小的硬币数，所以数组先初始化为较大的amount+1（最多需要amount+1枚硬币）
- 加一个虚拟的0行0列，第0行表示当前硬币为0，第0列表示当前金额数为0。第i行对应的硬币为第coins[i-1]个硬币
- 若金额大于当前硬币，则取装和不装的最小值
- 不装当前硬币：dp[i][j]=dp[i-1][j]
- 装当前硬币：dp[i][j]=dp[i][j-coins[i-1]]+1
- 注意dp[i][j]表示的是前i枚硬币凑成j块钱所需要的最小硬币数，这里的i已经包括了用和不用当前硬币, 所以不管是不是第一次用当前硬币，当前状态dp[i][j]都从dp[i][j-coins[i-1]]+1转移而来
- 若金额小于当前硬币，则不能装当前硬币：dp[i][j]=dp[i-1][j]
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount<0) return -1;
vector<vector<int>>dp(coins.size()+1,vector<int>(amount+1,amount+1));
for (int i = 0; i < coins.size()+1; ++i) {
dp[i][0]=0;
}
for (int i = 1; i < coins.size()+1; ++i) {
for (int j = 0; j < amount+1; ++j) {
if (j>=coins[i-1]){
dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
return (dp[coins.size()][amount]==amount+1)?-1:dp[coins.size()][amount];
}
};
方法2：一维dp数组
- 明确dp数组含义：凑好当前零钱数的最小硬币数量
- 明确 base case：dp[0]=0。 初始化时dp[i] 设为
float("inf")最大值 - 明确状态：零钱大小
- 明确选择：硬币。
if i>=coin时才做选择（零钱大小至少要比硬币值大）
class Solution(object):
def coinChange(self, coins, amount):
dp=[float("inf") for _ in range(amount+1)]
dp[0]=0
for i in range(1,amount+1):
for coin in coins: # 相当于在确定第i个值时，取所有（可行）硬币的状态转移的最小值+1
if i>=coin:
dp[i]=min(dp[i],dp[i-coin]+1)
return dp[-1] if dp[-1]!=float("inf") else -1 //#include <vector>
//#include <iostream>
//using namespace std;
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,amount+1);
dp[0]=0;
for (int i = 1; i < amount+1; ++i) {
for (int coin:coins) {
if (coin<=i)
dp[i]=min(dp[i],dp[i-coin]+1);
}
}
return (dp.back()==amount+1)?-1:dp.back();
}
};
//int main(){
// vector<int> coins={1, 2, 5};
// int s=Solution().coinChange(coins,11);
// cout<<s<<endl;
//}
