【测评中的编程题】方块涂色

2018/03/06 17:12
阅读数 107

题意是这样的:有N个方块,可以被涂成K种颜色。输入N*K矩阵,costs[n][k]代表第n个方块,涂成第k种颜色的花费。要求每相邻两个方块的颜色不同。求最小花费。

思路:没找到动态规划的更好方法,只好用递归来穷举了

 

 1 //返回n~N层的minCost,k表示n-1层被涂成第k种颜色。初始n=0,k=-1
 2 int minCost(vector<vector<int>>& costs,int n,int k)
 3 {
 4     int mintemp;
 5     map<int,int> mmin;
 6     for (int i= 0;i<costs[n].size();i++)
 7     {
 8         if (i != k)    //上一个方块被涂成第k种颜色
 9         {
10             if (n != (costs.size() - 1))
11                 mmin[costs[n][i]+minCost(costs, n + 1, i)] = i;
12             else
13                 mmin[costs[n][i]] = i;
14         }
15     }
16     return mmin.begin()->first;
17 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部