Leetcode动态规划模板

// 1.通用初始化
vector<int> dp(容量 + 1, base case1);
// 2.边界初始化
dp[0][0][...] = base case2
// 3.状态转移
for 状态1的个数
	for 状态2的个数
		for ...
			dp[状态1][状态2][...] = 求最值 or 求和(选择1, 选择2，...)

// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
for (int i = 0; i < 物品总数; i++)
    for (int j = 背包容量; j >= 物品i的重量; j--) {
        // 3.背包容量下的最值 = max(不装物品i最值, 装物品i的最值)
        dp[j] = max(dp[j], dp[j - 物品i的重量] + 物品i的价值);
    }
return dp[背包容量];

// 1.通用dp初始化
vector<int> dp(背包容量 + 1, INT_MIN);
// 2.边界dp初始化
dp[0] = 0; 
for (int i = 0; i < 物品总数; i++)
    for (int j = 背包容量; j >= 物品i的重量; j--) {
    	if (dp[i - 物品i的重量] == INT_MIN) continue;   // 因为不能有INT_MIN + 常数
        // 3.背包容量下的最值 = max(不装物品i最值, 装物品i的最值)
        dp[j] = max(dp[j], dp[j - 物品i的重量] + 物品i的价值);
    }
return dp[背包容量];

// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
// 2.边界dp初始化
dp[0] = 1;    // [关键]：根据状态转移方程，dp[0]须为1
for (int i = 0; i < 物品总数; i++)
    for (int j = 背包容量; j >= 物品i的重量; j--) {
        // 3.总组合数 = 不装物品i的组合数 + 装物品i的组合数
        dp[j] = dp[j] + dp[j - 物品i的重量];
    }
return dp[背包容量];

// 1.通用dp初始化
vector<int> dp(背包容量 + 1, false);
// 2.边界dp初始化
dp[0] = true;    // [关键]：根据状态转移方程，dp[0]须为true
for (int i = 0; i < 物品总数; i++)
    for (int j = 背包容量; j >= 物品i的重量; j--) {
        // 3.组合是否有 = 不装物品i的组合是否有 || 装物品i的组合是否有
        dp[j] = dp[j] || dp[j - 物品i的重量];
    }
return dp[背包容量];

// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
// 2.边界dp初始化
dp[0] = 1;    // [关键]：根据状态转移方程，dp[0]须为1
for (int j = 1; j <= 背包容量; j++) {
    for (int i = 0; i < 物品总数; i++)
        // 3.总组合数 = 不装物品i的排列数  + 装物品i的排列数 
        dp[j] = dp[j] + dp[j - 物品i的重量];
    }
return dp[背包容量];

// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
// 2.边界dp初始化
dp[0] = 1;    // [关键]：根据状态转移方程，dp[0]须为1
for (int i = 0; i < 物品总数; i++)
	for (int j = 物品i的重量; j <= 背包容量; j++) {
        // 3.总组合数 = 不装物品i的组合数 + 装物品i的组合数
        dp[j] = dp[j] = dp[j] + dp[j - 物品i的重量]; 
    }
return dp[背包容量];