leetcode256 粉刷房子 paint-house（dfs or dp）

• https://leetcode-cn.com/problems/paint-house

#include <stdio.h>
#include <algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<memory>
using namespace std;
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))


class Solution
{
public:

  vector < int >res_vector = { };
  void dfs (vector < vector < int > >nums, int index, int sum, int precolor)
  {
    if (index == nums.size ())
      {
	res_vector.push_back (sum);
	return;
      }
    for (int i = 0; i < 3; i++)
      {
	if (i != precolor)
	  {
	    dfs (nums, index + 1, sum + nums[index][i], i);
	  }
      }

  }

  int paint (vector < vector < int > >nums)
  {

    dfs (nums, 0, 0, 4);
    int maxValue = *min_element (res_vector.begin (), res_vector.end ());
    return maxValue;
  }

  int d_paint (vector < vector < int > >costs)
  {
    int n = costs.size();
    if (n == 0)
      return 0;
    int dp[n][3];
    dp[0][0] = costs[0][0];
    dp[0][1] = costs[0][1];
    dp[0][2] = costs[0][2];
    for (int i = 1; i < n; i++)
      {
	dp[i][0] = min (dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
	dp[i][1] = min (dp[i - 1][2], dp[i - 1][0]) + costs[i][1];
	dp[i][2] = min (dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
      }
    return min (min (dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
  }





};



int
main ()
{
  //Solution *myslo = new Solution();
  unique_ptr < Solution > myslo = unique_ptr < Solution > (new Solution ());
  vector < vector < int >>v1 = { {17, 2, 17},
  {1, 0, 5},
  {1400, 300, 19}
  };				// res = 22


  cout << myslo->paint (v1) << endl;//递归方法
  cout << myslo->d_paint(v1) << endl;//动态规划
  


  cout << "*************************************************************" <<
    endl;
  //delete myslo;
  return 0;
}

递归思路

粉刷房子

• dfs ，需要有一个记录深度的index
  dfs( vector nums, int index){
  if index==n
  res. push_back(sum);
  }

• dfs ，还需要一个保存当前结果的值sum
  dfs( vector< vector > nums, int index,int sum){
  if index=n
  res. push_back(sum);
  dfs( vector nums, index+1,sum+ num[index][0])
  }
  ………………………………………………………………

• void dfs( vector< vector > nums, int index,int sum){
  if index==n
  res. push_back(sum); return；
  dfs( vector nums, index+1,sum+ num[index][0])
  dfs( vector nums, index+1,sum+ num[index][1])
  dfs( vector nums, index+1,sum+ num[index][2])
  }

• 调用方式：void dfs( nums, 0,0)

………………………………

• void dfs( vector< vector > nums, int index,int sum,int precolor){
  if index==n
  res. push_back(sum); return；

  for
  if i != precokor
  dfs( vector nums, index+1,sum+ num[index][i])

  }

动态规划思路

• 一般的dp,dp[n]=f(dp[n-1], dp[n-2], ……,dp[0])

• 颜色不重复需要另一个纬度的控制，所以是二维动态规划

• 定义 dp[i][j] 表示前 i 个房子在最后一个房子选择颜色 j 的情况下的总成本。

• dp[i][0] = min (dp[i - 1][1], dp[i - 1][2]) + costs[i][0];

• dp[i][1] = min (dp[i - 1][2], dp[i - 1][0]) + costs[i][1];

• dp[i][2] = min (dp[i - 1][0], dp[i - 1][1]) + costs[i][2];