DP动态规划入门学习记录（二）

练习1：Paint House(dp)

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.

Note:
All costs are positive integers.

Example:

Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

英语真让人头大

翻译：

有一排n栋房子，每栋房子都可以涂上三种颜色中的一种：红色、蓝色或绿色。每栋房子刷上某种颜色的费用是不同的。你必须粉刷所有的房子，这样相邻的两栋房子就不会有相同的颜色。

用一个nx3成本矩阵来表示为每间房子涂上某种颜色的成本。例如，costs[0] [0]是将房屋0涂成红色的成本；costs[1] [2]是将房屋1漆成绿色的成本，依此类推……找出所有房屋的最低成本。

注：

所有代价都是正整数。

例子：

输入：[[17,2,17]，[16,16,5]，[14,3,19]]

输出：10

说明：将房屋0漆成蓝色，将房屋1漆成绿色，将房屋2漆成蓝色。

最低成本：2+5+3=10。

分析：

这样无法分解子问题 PASS！！

正确分析如下：

1.$f[i][j]$表示前i个房子且第i栋房子涂成第j种颜色的最小值

2.分解子问题

​ 1）$f[i][1]=min(f[i-1][2],f[i-1][3])+a[i][1]$;

​ 2）$f[i][2]=min(f[i-1][1],f[i-1][3])+a[i][2]$;

​ 3）$f[i][3]=min(f[i-1][1],f[i-1][2])+a[i][3]$;

3.边界

​ i=1时 $f[i][j]=a[i][j]$

4.计算顺序：从小到大

5.结果

​ $ans=min(f[n][1],f[n][2],f[n][3])$

代码：

#includeusing namespace std;int f[1005][1005];int n;int main(){cin>>n;for(int i=1;i>a>>b>>c;if(i==1){f[1][1]=a;f[1][2]=b;f[1][3]=c;continue;}f[i][1] = min(f[i-1][2],f[i-1][3])+a;f[i][2] = min(f[i-1][1],f[i-1][3])+b;f[i][3] = min(f[i-1][1],f[i-1][2])+c;}int min=0x3f3f3f3f;for(int i=1;i<=3;i++){if(f[n][i]<min)min=f[n][i];}cout<<min;return 0;}

我没有再创建a数组储存输入信息，这样更简便了（其实是我懒得写）

SO EASY！

动态规划真的好用，就是有点不好思考。

问题思考1：

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入格式

输入若干个数据（不超过100个）表示第 h i h_i hi​户人家金币的个数，

输出格式

输出能够盗取的最高金币数量

输入输出样例

输入 #1

1 2 3 1

输出 #1

4

输入 #2

2 7 9 3 1

输出 #2

12

说明/提示

示例 1：

输入：[1,2,3,1]

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1+ 3 = 4

示例 2：

输入：[2,7,9,3,1]

输出：12

解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

对于100%的数据 0 <= h[i] <= 400

分析：

1.定义状态 $f[i][0]$表示不偷,$f[i][1]$表示偷

2.分解子问题

​ $f[i][0]=max(f[i-1][0],f[i-1][1])$

​ $f[i][1]=f[i-1][0]$

3.结果

​ $ans=max(f[n][0],f[n][1])$

另一种思考方式：

1.定义状态

​ $f[i]$表示偷前i个房子能够获得的最大金额

2.分解子问题

​ $f[i]=max(f[i-2]+h[i],f[i-1])$

3.结果

​ $ans=max(f[x],f[x-1])$

灰常的简单！

给出第二种思考方法的代码：

#includeusing namespace std;int f[500];int h[500];int n;int main(){int k=1;while(cin>>h[k++]){int l=1;}f[1]=h[1];for(int i=1;i<=k;i++){f[i]=max(f[i-2]+h[i],f[i-1]);}cout<<max(f[k],f[k-1]);return 0;}

问我为啥不写第一种？？不想写

2022.4.29 13：25