上一次的动态规划的文章中（浅谈动态规划（一）——从lintcode刷题入门），借助lintcode上两个简单且典型的例子（Triangle和Climbing Stairs），阐述了动态规划的两个特点：1）最优子结构，和2）子问题重叠。这回来讲讲最近做lintcode上的几个难度稍微大一些的题目。这些题目也很符合动态规划的那两个特点。

先来看看第一个题目。

1.Paint Fence（栅栏染色）

题目描述：

There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint the fence.
Notice: n and k are non-negative integers.

例子：
Given n=3, k=2 return 6

item post 1 post 2 post 3
way1 0 0 1
way2 0 1 0
way3 0 1 1
way4 1 0 0
way5 1 0 1
way6 1 1 0

题目中要求给n个栅栏涂颜色，有k种颜色可以选择，限制条件是最多可以有两个相邻的栅栏颜色相同。

解题思路：

令ways[i]( n = 1, 2, 3, ..., n )表示涂到第i个栅栏时的所有的方法数。这样，题目就符合动态规划的两个特征（参考之前的那篇文章分析），就可以用动态规划求解。那么我们在涂第i个栅栏的时候，有两种涂色方式：1）和第i-1个栅栏的颜色相同；2）和第i-1个栅栏的颜色不同。在1）方式下，因为要保证最多只有两个相邻的栅栏颜色相同，所以第i个栅栏的颜色和第i-2个栅栏的颜色必然是不同的，那么此时有ways[i-2] * (k-1)中填涂的方式。在2）方式下，不需要考虑之前的栅栏的颜色，只要保证和i-1个栅栏颜色不同即可，此时有ways[i-1] * (k-1）种方法。所以有状态转移方程：

ways[i] = ways[i-2] * (k-1) + ways[i-1] * (k-1)

同时发现，每次只要用到相邻的3个栅栏的方法数就可以了，这样可以减少空间的使用。所以代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int numWays(int n, int k) {
	// Write your code here
	if (n == 0 || k == 0)
		return 0;
		
	if (n == 1)
		return k;
	if (n == 2)
		return k * k;
		
	int ways[3] = {0}; // 辅助数组，只使用3个变量即可
	ways[0] = k;
	ways[1] = k * k;
		
	// 动态规划步骤
	for (int i = 2; i < n; i++)
	{
		ways[2] = (k-1) * (ways[0] + ways[1]); // 依据相邻的两个栅栏的填涂方法数来求解第3个栅栏的填涂方法数
		ways[0] = ways[1];
		ways[1] = ways[2];
	}
		
	return ways[2];
}

这道题虽然也是简单的，但是因为限制条件的运用比较巧妙，所以给贴出来了。接下来看看下一题。

2.House Robber（打劫房屋）

题目描述：

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

例子：
Given [3, 8, 4], return 8.

题目要求从n个房屋中找出一些房屋取走里面财产，找到财产最大的总值，限制条件是不能有相邻的房屋同时被偷盗。

这道题虽然是道中等题，不过思路也很清晰，动态规划的两个特征也非常明显。令money[i]( i = 1, 2, ..., n )表示在偷第i个房屋时的最大值，那么在偷第i个房屋时，需要比较的只是money[i-1]和money[i-2] + A[i]值的大小(A[i]是第i个房屋的财产值)，因为相邻的两个房屋不可能同时被偷。所以，状态转移方程为：

money[i] = max(money[i-1], money[i-2] + A[i])

同样，我们发现每次比较时，只需要保留最近两次的最大值即可，那么优化后的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
long long houseRobber(vector<int> A) {
	// write your code here
	int n = A.size();
	if (n == 0)
		return 0;
	
	if (n == 1)
		return A[0];
	
	// 辅助数组
	long long money[3] = {0};
	money[0] = 0;
	money[1] = A[0];
	
	// 动态规划步骤
	for (int i = 2; i <= n; i++)
	{
		money[2] = max(A[i-1] + money[0], money[1]);
		money[0] = money[1];
		money[1] = money[2];
	}
	
	return money[2];
}

最后来看第3题。

3.Paint House（房屋染色）

题目描述：

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Notice: All costs are positive integers.

例子：

Given costs = [[14,2,11],[11,14,5],[14,3,10]] return 10

house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10

题目要求给n个房子粉刷颜色，找到最小的费用。粉刷时有3种颜色可供选择，而粉刷不同的颜色的费用是不同的，限制条件是相邻的两个房子的颜色不能相同。这道题目其实和上一道题目有点类似，均为相邻的两个有限制，不过这个在动态规划的时候，比较的是粉刷的不同的颜色。同样的方法，令value[i][j](i = 1, 2, ..., n; j = 1, 2, 3)表示正在粉刷第i个房子的时候颜色为j时的总费用（之前粉刷的位置均保证了费用最小）。为了避免相邻的两个房子粉刷的颜色相同，在粉刷每一层的时候，还要和前一层粉刷的颜色比较。那么在粉刷第i个房屋颜色为j时的状态转移方程为：

value[i][j] = min(costs[i][j] + value[i-1][k]), k = 1, 2, 3; k != j

上式中k是上一层粉刷不同颜色到达最小值时的不同颜色。在粉刷时要保证相邻的两层颜色不相同，所以k != j。

有了状态转移方程，题目的代码就好写了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int minCost2(vector<vector<int> > &costs)
{
	int n = costs.size();
	if (n == 0)
		return 0;
	
	int i, j, k;
	int temp;
	int minValue = INT_MAX;
			
	for (j = 0; j < 3; j++) 
            if (minValue > costs[0][j])
	        minValue = costs[0][j];
					   
	if (n == 1)
		return minValue;
	vector<vector<int> > value(n, vector<int>(3, INT_MAX)); // 辅助数组，初始化时每个位置均为INT_MAX
	// 动态规划步骤
	for (i = 0; i < n; i++)
	{
		if (i == 0)
		{
			for (j = 0; j < 3; j++)
				value[i][j] = costs[i][j];
			continue;
		}
		// 找出相邻两层不相同时，粉刷不同颜色的最小值
		for (j = 0; j < 3; j++)
		{
			minValue = INT_MAX;
			for (k = 0; k < 3; k++) // 上一层粉刷不同颜色时对应的最小值
			{
				if (k == j) // 跳过相同颜色
					continue;
				// 找出最小值
				temp = costs[i][j] + value[i-1][k];
				if (temp < minValue)
					minValue = temp;
			}
			value[i][j] = minValue;
		}
	}
	// 找出粉刷完最后一个房屋时的最小费用
	minValue = INT_MAX;
	for (j = 0; j < 3; j++) 
            if (minValue > value[n-1][j])
		minValue = value[n-1][j];
	return minValue;
}

同样，代码也可以优化以减少空间消耗，在这里就不再将最后结果贴出来了。

好了，这就是这次的全部内容。这些题目是我在刷lintcode中遇到的动态规划特征比较明显的题目，且比《浅谈动态规划（一）——从lintcode刷题入门》里面的一些题目稍微难点。希望能够给初接触动态规划的童鞋一点参考。

参考资料：
lintcode
1.Paint Fence（栅栏染色）
2.House Robber（打劫房屋）
3.Paint House（房屋染色）