9.7途虎养车第三题求问一下解法

看着像状态dp

经典的动态规划

二维dp？每列三个元素维护以三种结尾的最小值

典型的dp了，用记忆化搜索很快写出来 dp[][]=new [][]; int dfs( int i,int j,int k){ if( dp[i][j]!=-1) return dp[i][j]; int sum=0; for( t -->k ){ if( t!=j) sum+=dfs(i+1,t,k) } dp[i][j]=sum; return sum; }

上面写漏了些东西，for循环里面是这样sum=min( sum, dfs(i,t,k)+cost[i][t] );思路就是:当涂到第i辆车时，有j种颜色，那么最小花费就是dfs(i,j,k);