Leetcode 322：零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例

示例1：

输入: coins = [1, 2, 5], amount = 11输出: 3
解释: 11 = 5 + 5 + 1

示例2：

输入: coins = [2], amount = 3输出: -1

解题思路

这个问题很明显是一种0-1背包问题，利用动态规划的思想，写出其状态转移方程为：

dp(n)=0,if n=0;
dp(n)=min(dp(n),dp(i-coin)+1),n>0

那么接下来，代码实现就自然而然的事情了。

代码实现

int coinChange(vector<int>& coins, int amount) {
	vector<int> dp(amount + 1, amount + 1);
	dp[0] = 0;
	for (int i = 1; i <= amount; i++)
	{
		for (int c : coins)
		{
			if (c <= i)
				dp[i] = min(dp[i], dp[i - c] + 1);
		}
	}
	return dp[amount] > amount ? -1:dp[amount];

}

性能

时间复杂度：O(amount*coins)

复杂度配图

Leetcode 337：打家劫舍（3）

题目描述

小偷发现了一个可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

解题思路

这道升级版的树状动态规划问题也可以由一维的dp延伸来，只是情况稍微复杂一些，每一个节点的dp值与三层二叉树的结点dp值相关。对于下图所示的一棵三层满二叉树来说：
1
/ \
2 3
/ /
4 5 6 7

在每个结点的金额非负的情况下，且要保证取值结点不相邻，只可能有四种最大的取值方式：

结点2 + 结点3
结点1 + 结点4 + 结点5 + 结点6 + 结点7

那么我们可以自底向上递归进行这个dp运算，令dp[i]代表以i结点为根节点的子树的最大偷窃金额值，计算结束后将dp值直接保存在i结点的val值当中返回。可以推出状态转移方程为：

1	dp[root] = Max(dp[l]+dp[r], root.val+dp[ll]+dp[lr]+dp[rr]+dp[rl], dp[l]+dp[rl]+dp[rr], dp[r]+dp[lr]+dp[rl]);

分别对应上述四种情况。而观察发现，在dp[l]和dp[r]的计算中实际已经包含了dp[ll]、dp[lr]、dp[rr]、dp[rl]的取舍情况，因此可以简化为前两种情况。状态转移方程简化为：

1	dp[root] = Max(dp[l]+dp[r], root.val+dp[ll]+dp[lr]+dp[rr]+dp[rl]);

为了方便运算，我们一般会为dp数组赋予初值。在树状dp中同样，我们需要将每一个非叶结点作为根节点的子树构造成一棵三层满二叉树方便运算。

对于叶子结点，我们给其添加值为0的左右子结点。

对于左/右子树为空的非叶节点，我们在其左/右添加一棵两层值为0的满二叉树。

代码实现

    TreeNode* solution(TreeNode* root)
{
	if (root == nullptr)
	{
		TreeNode* nnode = new TreeNode(0);
		return solution(nnode);
	}

	if (root->left == nullptr && root->right == nullptr)
	{
		root->left = new TreeNode(0);
		root->right = new TreeNode(0);
		return root;
	}

	root->left = solution(root->left);
	root->right = solution(root->right);
	root->val = max(root->left->val + root->right->val, root->val + root->left->left->val + root->left->right->val + root->right->left->val + root->right->right->val);
	return root;
}

int rob(TreeNode* root) {

	return solution(root)->val;

}