一共有n个房子，有三种颜色可以选，要求相邻的房子不能相同颜色，求最小的花费
costs = [[17,2,17],[16,16,5],[14,3,19]]
dfs
dfs(costs,cur,j):表示第cur个房子，选择第j种颜色的最小花费
class Solution {
public int minCost(int[][] costs) {
int res=Integer.MAX_VALUE;
for(int j=0;j<3;j++){
res=Math.min(res,dfs(costs,0,j));
}
return res;
}
public int dfs(int[][] costs,int cur,int j){
if(cur==costs.length){
return 0;
}
int res=Integer.MAX_VALUE;
for(int i=0;i<3;i++){
if(i!=j){
res=Math.min(res,dfs(costs,cur+1,i)+costs[cur][j]);
}
}
return res;
}
}
记忆化搜索
mem[cur][j]表示当cur间房选择j种颜色的时候，后面所有的房子的最小花费
class Solution {
public int minCost(int[][] costs) {
int res=Integer.MAX_VALUE;
int[][] mem=new int[costs.length][3];
for(int j=0;j<3;j++){
res=Math.min(res,dfs(costs,0,j,mem));
}
return res;
}
public int dfs(int[][] costs,int cur,int j,int[][] mem){
if(cur==costs.length){
return 0;
}
if(mem[cur][j]!=0){
return mem[cur][j];
}
int res=Integer.MAX_VALUE;
for(int i=0;i<3;i++){
if(i!=j){
res=Math.min(res,dfs(costs,cur+1,i,mem)+costs[cur][j]);
}
}
mem[cur][j]=res;
return res;
}
}
dp
dp[cur][j]表示当第cur间房选择第j种颜色的时候，其后所有的房子的花费
class Solution {
public int minCost(int[][] costs) {
int[][] dp=new int[costs.length][3];
for(int i=0;i<3;i++){
dp[costs.length-1][i]=costs[costs.length-1][i];
}
for(int i=costs.length-2;i>=0;i--){
for(int j=0;j<3;j++){
if(j==0){
dp[i][j]=costs[i][j]+Math.min(dp[i+1][1],dp[i+1][2]);
}
if(j==1){
dp[i][j]=costs[i][j]+Math.min(dp[i+1][0],dp[i+1][2]);
}
if(j==2){
dp[i][j]=costs[i][j]+Math.min(dp[i+1][1],dp[i+1][0]);
}
}
}
return Math.min(dp[0][0],Math.min(dp[0][1],dp[0][2]));
}
}
dp[cur][j]:表示从前往后进行递推
class Solution {
public int minCost(int[][] costs) {
int[][] dp=new int[costs.length][3];//dp[i][j]表示前i间房子 在第i间房选择第j种颜色时的最小花费
for(int i=0;i<3;i++){
dp[0][i]=costs[0][i];
}
for(int i=1;i<costs.length;i++){
for(int j=0;j<3;j++){
if(j==0){
dp[i][j]=costs[i][j]+Math.min(dp[i-1][1],dp[i-1][2]);
}
if(j==1){
dp[i][j]=costs[i][j]+Math.min(dp[i-1][0],dp[i-1][2]);
}
if(j==2){
dp[i][j]=costs[i][j]+Math.min(dp[i-1][0],dp[i-1][1]);
}
}
}
return Math.min(dp[costs.length-1][0],Math.min(dp[costs.length-1][1],dp[costs.length-1][2]));
}
}
最小化目标值与所选元素之和的绝对值差
最小化目标值与所选元素之和的绝对值差
dp[i][j]表示对于前i行 所选元素和为j是否存在
class Solution {
public static int minimizeTheDifference(int[][] mat, int target) {
int n=mat.length;int m=mat[0].length;
int maxsum=0;
List<Boolean> dp=new ArrayList<Boolean>();
dp.add(true);
for(int i=0;i<n;i++){
int maxv=Integer.MIN_VALUE;
for(int j=0;j<m;j++){
if(mat[i][j]>maxv){
maxv=mat[i][j];
}
}
Boolean[] nums=new Boolean[maxsum+maxv+1];
Arrays.fill(nums,false);
List<Boolean> g=new ArrayList<Boolean>(Arrays.asList(nums));
for(int j=0;j<m;j++){
for(int k=mat[i][j];k<=mat[i][j]+maxsum;k++){
g.set(k,g.get(k)||dp.get(k-mat[i][j]));
}
}
dp=g;
maxsum+=maxv;
}
int res=Integer.MAX_VALUE;
for(int i=0;i<=maxsum;i++){
if(dp.get(i)&&Math.abs(i-target)<res){
res=Math.abs(i-target);
}
}
return res;
}
}
方式二 记忆化搜索
class Solution {
int res=Integer.MAX_VALUE;
boolean[][] dp;
int n,m;
public int minimizeTheDifference(int[][] mat, int target) {
n=mat.length;m=mat[0].length;
dp=new boolean[n+10][5000];
dfs(0,0,target,mat);
return res;
}
public void dfs(int i,int now,int target,int[][] mat){
if(i==n){
res=Math.min(res,Math.abs(now-target));
return;
}
if(now-target>res||dp[i][now]){//记忆化的作用类似于剪枝
return;
}
dp[i][now]=true;
for(int j=0;j<m;j++){
dfs(i+1,now+mat[i][j],target,mat);
}
}
}
统计所有的可行路径
方式一：记忆化搜索
class Solution {
int[][] memo;
int res=0;
int MOD=1000000007;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
//记忆化搜索
int n=locations.length;
memo=new int[n][fuel+1];
for(int i=0;i<n;i++){
Arrays.fill(memo[i],-1);
}
return dfs(locations,start,finish,fuel);
}
public int dfs(int[] locations,int start,int finish,int fuel){
if(memo[start][fuel]!=-1){
return memo[start][fuel];
}
//如果不能一步到达
//返回之前将对应的记忆化数组修改
memo[start][fuel]=0;
if(Math.abs(locations[start]-locations[finish])>fuel){
return 0;
}
//对于下一个可能到达的位置
int n=locations.length;
for(int i=0;i<n;i++){
if(start!=i){
if(Math.abs(locations[start]-locations[i])<=fuel){
memo[start][fuel]+=dfs(locations,i,finish,fuel-Math.abs(locations[start]-locations[i]));
memo[start][fuel]%=MOD;
}
}
}
if(start==finish){
memo[start][fuel]+=1;
memo[start][fuel]%=MOD;
}
return memo[start][fuel];
}
}
方式二：dp
统计所有的可行路径
循环顺序，对应维度顺序
单个维度的递增递减顺序
class Solution {
int MOD=1000000007;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
//通过dp[][]方式进行路径问题
int n=locations.length;
int[][] dp=new int[n][fuel+1];
//进行初始化
for(int i=0;i<=fuel;i++){
dp[finish][i]=1;//当前就在目的地，对应的路径为1
}
for(int j=0;j<=fuel;j++){//需要先固定j,计算所有的i,才能计算对应的dp[i][j]，所以循环的顺序遵循先对j进行枚举
for(int i=0;i<n;i++){
// for(int j=0;j<=fuel;j++){
for(int k=0;k<n;k++){
if(k!=i&&j>=Math.abs(locations[k]-locations[i])){
dp[i][j]+=dp[k][j-Math.abs(locations[k]-locations[i])];
dp[i][j]%=MOD;
}
}
}
}
return dp[start][fuel];
}
}
