leetcode动态规划入门,leet code

LeetCode 房屋染色 动态规划 问题描述

假如有一排房子共 n 个每个房子可以被粉刷成 k 种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n*k 的矩阵来表示的。
例如costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费以此类推。请你计算出粉刷完所有房子最少的花费成本。
注意
所有花费均为正整数。

输入输出示例

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色1 号房子粉刷成 2 号颜色。最少花费: 1 4 5;
或者将 0 号房子粉刷成 2 号颜色1 号房子粉刷成 0 号颜色。最少花费: 3 2 5.

图解思路

令dp[i][j]表示为第i- 1号房子染第j号颜色时的最小费用。

代码实现

public class Solution {    /**     * param costs: n x k cost matrix     * return: an integer, the minimum cost to paint all houses     */    public int minCostII(int[][] costs) {        int n  costs.length;        if(n  0)            return 0;        int k  costs[0].length;        if(k  0)            return 0;                //数组定义dp[i][j] 表示的是 0 -> i - 1号房刷j种颜色的最小花费        int dp[][]  new int[n  1][k];        int ans  Integer.MAX_VALUE;                /**        当且仅当最小值下标不等于j时        状态方程 dp[i][j]  min(dp[i - 1][0..k-1])  cost[i - 1][j]        **/                for(int i  1; i < n; i) {            int firMin  Integer.MAX_VALUE, secMin  Integer.MAX_VALUE;            int firIdx  0, secIdx  0;                        //寻找最小值和次小值以及他们的下标            for(int j  0; j < k; j) {                if(dp[i - 1][j] < firMin) {                    secMin  firMin;                    secIdx  firIdx;                    firMin  dp[i - 1][j];                    firIdx  j;                } else if(dp[i - 1][j] < secMin) {                    secMin  dp[i - 1][j];                    secIdx  j;                }            }                        for(int j  0; j < k; j) {            //因为相邻房屋不能涂相同颜色所以当j等于最小值下标时要选择次小值                if(j ! firIdx) {                    dp[i][j]  firMin  costs[i - 1][j];                } else {                    dp[i][j]  secMin  costs[i - 1][j];                }            }        }                for(int i  0; i < k; i) {            ans  Math.min(ans, dp[costs.length][i]);        }                return ans;    }}