动态规划&回溯算法

题目：

有个穷困的艺术家。他画了一幅超现实主义的作品《方块手拉手》。现在他已经把图画中手拉手的一排大小不一的方块都画出来了。现在要考虑上颜色了。可惜他手中的钱并不多了。但是他是个有追求的人，他希望这幅画中每两个相邻的方块的颜色是不一样的。你能帮他计算一下把这幅画上色后，最少需要花多少钱么。

输入 N个方块，K个颜色

接下来每列是各个方块染成不同颜色的价钱

输出 最少花的钱

例：
输入：
4 3
2 3 2
9 1 4
7 8 1
2 8 3
输出：
6

// 动态规划
#include <iostream>
#include <vector>

using namespace std;

int minCost(vector<vector<int> >& cost) {
    int N = cost.size();
    int K = cost[0].size();
    vector<vector<int> > res(N, vector<int>(K, 0));
    for (int i = 0; i < K; ++i) {
        res[0][i] = cost[0][i];
    }

    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < K; ++j) {
            int min = INT_MAX;
            for (int k = 0; k < K; ++k) {
                if ((k != j) && res[i-1][k] < min) min = res[i-1][k];
            }
            res[i][j] = cost[i][j] + min;
        }
    }

    int min = INT_MAX;
    for (int i = 0; i < K; ++i) {
        if (res[N-1][i] < min) min = res[N-1][i];
    }

    return min;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int> > cost;

    while(N--) {
        vector<int> tmp;
        int a;
        int k = K;
        while (k--) {
            cin >> a;
            tmp.push_back(a);
        }
        cost.push_back(tmp);
    }

    cout << minCost(cost) << endl;
    return 0;
}

// 回溯算法
#include <iostream>
#include <vector>

using namespace std;

int ans = INT_MAX;

bool isNotNear(int i, int depth, vector<int>& path) {
    if (depth != 0 && i == path[depth - 1]) return false;
    return true;
}

void minCostCore(vector<vector<int> >& cost, int depth, int sum, vector<int> path) {
    if (depth == cost.size()) {
        if(ans > sum) ans = sum;
        return;
    }

    for (int i = 0; i < cost[0].size(); ++i) {
        path[depth] = cost[depth][i];
        if (isNotNear(i, depth, path)) {
            minCostCore(cost, depth+1, sum+cost[depth][i], path);
        }
        path[depth] = -1;
    }
}

int minCost(vector<vector<int> >& cost) {
    int N = cost.size();
    int K = cost[0].size();
    vector<int> path(cost.size(), -1);
    minCostCore(cost, 0, 0, path);
    return ans;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int> > cost;

    while(N--) {
        vector<int> tmp;
        int a;
        int k = K;
        while (k--) {
            cin >> a;
            tmp.push_back(a);
        }
        cost.push_back(tmp);
    }

    cout << minCost(cost) << endl;
    return 0;
}