1.求最值型动态规划

动态规划的组成部分：

1.确定状态：a: 最后一步（最优策略中使用的最后一枚硬币ak）

                     b:化成子问题（最少的硬币拼出更小的面值amount-ak）

2转移方程：

for(int i=0;i<coins.length;i++){

f[i] = min(f[i],f[i-coins[i]]+1)  f[i-coins[i]] 要满足使用之前的硬币  能够拼出来   也就是 f[i-coins[i]]!=Integer.Max,还有 i-coins[i]>0   

}

3.初始条件及边界情况

f[0]=0;   如果不能凑出来  赋值无限大 f[y]=Integer_Max;

4.计算顺序

f[0]、f[1]、f[2] ......

 

代码： 原题 lintcode 669

public int coinChange(int[] coins, int amount) { // write your code here int[] dp = new int[amount+1]; int n =coins.length; dp[0]=0; for (int i = 1; i <=amount ; i++) { dp[i] = Integer.MAX_VALUE; for (int j = 0; j <n; j++) { if (i>=coins[j]&&dp[i-coins[j]]!=Integer.MAX_VALUE){ dp[i] =Math.min(dp[i-coins[j]]+1,dp[i]); } } } if (dp[amount]==Integer.MAX_VALUE){ dp[amount]=-1 ; } return dp[amount]; }

2.存在性动态规划

1.确定状态：a.最后一步：如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步

                     b.这一步从石头i跳过来  i<n-1

                    (两个条件：青蛙可以跳到石头i，最后一步不超过跳跃的最大距离 ：  n-1-i<=ai   i+ai>=n-1) 

                    c.子问题 青蛙能不能跳到 石头 i ；

                     d. 状态  青蛙能不能跳到 石头i   f[i]

2.状态转移方程

                   

3初始条件和边界情况

f[j] 表示青蛙能不能跳到石头j

初始条件 f[0] = true,青蛙一开始就在石头0

4.计算顺序 从小到大 依次计算

public static boolean canJump(int[] A) { if (A == null || A.length == 0) return false; int n = A.length; boolean[] f = new boolean[n]; f[0] =true; for (int j = 1; j <n ; j++) { for (int i = 0; i <j ; i++) { if (f[i]&&i+A[i]>=j){ f[j]=true; break; } } } return f[n-1]; }

 

 

动态规划题目特点

 

 

Lintcode 115：Unique Path II

public static int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; if (m==0) return 0; int n = obstacleGrid[0].length; if (n==0 ) return 0; int[][] f =new int[m][n]; for (int i = 0; i <m ; i++) { for (int j = 0; j <n ; j++) { if (obstacleGrid[i][j]==1){ f[i][j]=0; }else { if (i==0&&j==0){ f[i][j]=1; }else { f[i][j]=0; if (i>0){ f[i][j]+=f[i-1][j]; } if (j>0){ f[i][j]+=f[i][j-1]; } } } } } return f[m-1][n-1]; }

 

 LintCode 515

1确定状态

最后一步：最右策略中房子n-1 一定染了 红绿蓝中的一种

 

 

public int minCost(int[][] costs) { if (costs.length<1||costs[0].length<1||costs==null) return 0; // write your code here int m = costs.length; int[][] dp= new int[m][3]; //第 i 个房子的 花费 0 红 1 绿 2 蓝 dp[0][0] = costs[0][0]; dp[0][1] = costs[0][1]; dp[0][2] = costs[0][2]; for (int i = 1; i <m ; i++) { dp[i][0] =Math.min(dp[i-1][1]+costs[i][0],dp[i-1][2]+costs[i][0]); dp[i][1] =Math.min(dp[i-1][0]+costs[i][1],dp[i-1][2]+costs[i][1]); dp[i][2] =Math.min(dp[i-1][0]+costs[i][2],dp[i-1][1]+costs[i][2]); } return Math.min(Math.min(dp[m-1][1],dp[m-1][0]),dp[m-1][2]); }

 

LintCode 512

 

 

 

public int numDecodings(String ss) { char[] s =ss.toCharArray(); int n = ss.length(); int[] f = new int[n+1]; if (n==0 ) return 0; f[0] =1; for (int i = 1; i <=n ; i++) { f[i]=0; int t = s[i-1]-'0'; if (t>=1&&t<=9){ f[i]+=f[i-1]; } if (i>=2){ t=(s[i-2]-'0')*10+(s[i-1]-'0'); if (t>=10&&t<=26){ f[i]+=f[i-2]; } } } return f[n]; }

 

 

 

 

 

public int longestIncreasingContinuousSubsequence(int[] A) { // write your code here int n= A.length; if(n<=1){return n;} int[] f =new int[n+1]; f[0]=1; int max =Integer.MIN_VALUE; for (int i = 1; i <n ; i++) { f[i]=1; if (A[i-1]<A[i]){ f[i]=f[i-1]+1; } max=Math.max(f[i],max); } f[n-1]=1; for (int i = n-2; i >=0 ; i--) { f[i] = 1; if (A[i]>A[i+1]){ f[i]=f[i+1]+1; } max=Math.max(f[i],max); } return max; } int result = 0; public int longestIncreasingContinuousSubsequence2(int[] A) { int n =A.length; if (n<=1) return n; calc(A,n); int i,j,t; i=0; j=n-1; while (i!=j){ t=A[i]; A[i] = A[j]; A[j] = t; ++i; --j; } calc(A,n); return result; } private void calc(int[] a, int n) { int[] f = new int[n]; int i,j; for ( i = 0; i <n ; i++) { f[i]=1; if (i>0&&a[i-1]<a[i]) f[i]=f[i-1]+1; result = Math.max(result,f[i]); } } //优化 private void calc2(int[] a, int n) { int[] f = new int[2]; int i; int old,now = 0; for ( i = 0; i <n ; i++) { old =now; now =1-now; f[now]=1; if (i>0&&a[i-1]<a[i]) f[now]=f[old]+1; result = Math.max(result,f[now]); } }

 

 

public int minPathSum(int[][] grid) { // write your code here int m = grid.length; int n = grid[0].length; int[][] f = new int[m+1][n+1]; f[0][0]=grid[0][0]; for (int i = 0; i <m ; i++) { for (int j = 0; j <n ; j++) { if (i==0&&j>0) f[i][j] = f[i][j-1]+grid[i][j]; if (j==0&&i>0) f[i][j] = f[i-1][j]+grid[i][j]; if (i>0&&j>0){ f[i][j]=Math.min(f[i-1][j],f[i][j-1])+grid[i][j]; } } } return f[m-1][n-1]; }

 

 

 

//优化 public int minPathSum(int[][] g) { if (g==null||g.length==0||g[0].length==0){ return 0; } int m = g.length; int n =g[0].length; int[][] f = new int[2][n]; int old =1,now =0; int i,j,t1,t2; for ( i = 0; i <m ; i++) { old=now; now=1-now; for ( j = 0; j <n ; j++) { if (i==0&j==0) { f[now][j] =g[i][j]; continue; } f[now][j] = g[i][j]; if (i>0){ t1 = f[old][j]; }else { t1=Integer.MAX_VALUE; } if (j>0){ t2=f[now][j-1]; }else { t2=Integer.MAX_VALUE; } if (t1<t2){ f[now][j] += t1; }else { f[now][j] += t2; } } } return f[now][n-1]; }

 

 

 

 

 

 

 

 

 

我的做法： 

public int maxKilledEnemies(char[][] grid) { if (grid==null||grid.length<1) return 0; int m = grid.length; int n = grid[0].length; int[][] f_up = new int[m+1][n+1]; int[][] f_down = new int[m+1][n+1]; int[][] f_left = new int[m+1][n+1]; int[][] f_right = new int[m+1][n+1]; //左到右 for (int i = 0; i <m ; i++) { for (int j = 0; j <n ; j++) { if (j==0){ f_left[i][j]=grid[i][j]=='E'?1:0; }else if (grid[i][j]=='E'){ f_left[i][j] = f_left[i][j-1]+1; }else if (grid[i][j]=='W'){ f_left[i][j] = 0; }else if (grid[i][j]=='0'){ f_left[i][j] = f_left[i][j-1]; } } } // 上到下 for (int i = 0; i <m ; i++) { for (int j = 0; j <n ; j++) { if (i==0){ f_up[i][j]=grid[i][j]=='E'?1:0; }else if (i>0&&grid[i][j]=='E'){ f_up[i][j] = f_up[i-1][j]+1; }else if (grid[i][j]=='W'){ f_up[i][j] = 0; }else if (i>0&&grid[i][j]=='0'){ f_up[i][j] = f_up[i-1][j]; } } } //从 右到 左 扫描 for (int i = 0; i <m ; i++) { for (int j = n-1; j >=0 ; j--) { if (j==n-1){ f_right[i][j]=grid[i][j]=='E'?1:0; }else if (grid[i][j]=='E'){ f_right[i][j] =f_right[i][j+1] + 1; }else if (grid[i][j]=='W'){ f_right[i][j] = 0; }else if (grid[i][j]=='0'){ f_right[i][j] = f_right[i][j+1]; } } } //从下往上扫 for (int i = m-1; i >=0 ; i--) { for (int j = 0; j <n ; j++) { if (i==m-1){ f_down[i][j]=grid[i][j]=='E'?1:0; }else if (grid[i][j]=='E'){ f_down[i][j] = f_down[i+1][j]+1; }else if (grid[i][j]=='W'){ f_down[i][j] = 0; }else if (grid[i][j]=='0'){ f_down[i][j] = f_down[i+1][j]; } } } int max =0; //只有 0处可以放炸弹 for (int i = 0; i <m ; i++) { for (int j = 0; j <n ; j++) { if (grid[i][j]=='0'){ int ans =0; if (i==0&&j==0){ // 只有 下 右 ans = f_right[i][j+1]+f_down[i+1][j]; }else if (i==0){ // 左右下 三条路 ans = f_left[i][j-1] + f_right[i][j+1] + f_down[i+1][j]; } else if (j==0){ // 上 下 右 ans =f_up[i-1][j]+f_down[i+1][j] +f_right[i][j+1]; }else if (i==m-1){ //上 左 右 ans = f_up[i-1][j]+f_left[i][j-1]+f_right[i][j+1]; }else if (j==n-1){// 上 下 左 ans = f_up[i-1][j]+f_down[i+1][j]+f_left[i][j-1]; }else { ans = f_up[i-1][j] + f_down[i+1][j] +f_left[i][j-1] +f_right[i][j+1]; } max = Math.max(max,ans); } } } return max; }

只开 两个 数组的方法   其他 四个方向一样

 

 

 

 

 

 

 

 

 

public int[] countBits(int num) { // write your code here int n = num; int[] f= new int[n+1]; f[0]=0; for (int i = 1; i <n+1 ; i++) { f[i]=f[i>>1]+(i%2==1?1:0); } return f; }

 

2

 

public int minCostII(int[][] costs) { if (costs==null||costs.length<1||costs[0].length<1) return 0; // write your code here int n= costs.length; // n 栋房子 int k = costs[0].length; // k种颜色 int[][] f = new int[n][k]; //相邻房屋颜色不能相同 for (int i = 0; i <k ; i++) { f[0][i] = costs[0][i]; } int allMin = Integer.MAX_VALUE; for (int i = 1; i <n ; i++) { for (int j = 0; j <k ; j++) { int min = Integer.MAX_VALUE; //给它染 第 就 j 号 颜色 for (int l = 0; l <k ; l++) { if (l!=j){ min =Math.min(min,f[i-1][l]+costs[i][j]); } } f[i][j]=min; } } for (int i = 0; i <k ; i++) { allMin=Math.min(f[n-1][i],allMin); } return allMin; }

//优化版本 

public int minCostII(int[][] A) { if (A==null||A.length == 0 ) return 0; int n = A.length; int k = A[0].length; int[][] f= new int[n+1][k]; int min1,min2; int index1 = 0,index2=0; for (int i = 1; i <=n ; i++) { min1=min2 = Integer.MAX_VALUE; for (int j = 0; j <k ; j++) { //求出最小值和次小值 if (f[i-1][j]<min1){ min2=min1; index2=index1; min1 = f[i-1][j]; index1=j; } else if (f[i-1][j]<min2){ min2 = f[i-1][j]; index2=j; } } for (int j = 0; j <k ; j++) { if (index1!=j){ f[i][j] =f[i-1][index1] +A[i-1][j]; }else { f[i][j] = f[i-1][index2]+A[i-1][j]; } } } int min =Integer.MAX_VALUE; for (int i = 0; i <k ; i++) { min=Math.min(f[n][i],min); } return min; }

 

 

 

 

public long houseRobber(int[] A) { if (A==null||A.length<1) return 0; // write your code here int n = A.length; long[] f = new long[n+1]; if (n==1)return A[0]; if (n==2) return Math.min(A[0],A[1]); f[0] = 0; f[1] = A[0]; for (int i = 2; i <=n ; i++) { f[i] =Math.max( f[i-2]+A[i-1],f[i-1]); } long max = 0 ; for (int i = 0; i <=n ; i++) { max = Math.max(max,f[i]); } return max; }

优化版本：

public long houseRobber(int[] A) { if (A == null || A.length < 1) return 0; int n = A.length; long[] f = new long[3]; if (n == 1) return A[0]; if (n == 2) return Math.min(A[0], A[1]); f[0] = 0; f[1] = A[0]; for (int i = 2; i <= n; i++) { f[2] =Math.max(f[0] + A[i-1],f[1]); f[0]=f[1]; f[1]=f[2]; } return Math.max(f[2],f[1]); }

 

 

 

public int houseRobber2(int[] A) { if (A == null || A.length < 1) return 0; int n = A.length; int[] f = new int[n+1]; if (n == 1) return A[0]; if (n == 2) return Math.min(A[0], A[1]); //选了 1 f[0] = 0; f[1] = A[0]; int max = 0; for (int i = 2; i <n; i++) { f[i] =Math.max(f[i-2] + A[i-1],f[i-1]); max =Math.max(f[i],max); } //选了 第n个 f[1] = 0; for (int i = 2; i <=n ; i++) { f[i] =Math.max(f[i-2] + A[i-1],f[i-1]); max =Math.max(f[i],max); } return max; }

 

 

 

public int maxProfit(int[] prices) { int n = prices.length ; int[] f_min=new int[n+1]; // i 前面的包括i 最小值 是多少 int[] f_max = new int[n+1]; //i 以后的最大值 是多少 f_min[0] = prices[0]; for (int i = 1; i <n ; i++) { if (f_min[i-1]>prices[i]){ f_min[i] = prices[i]; }else { f_min[i]= f_min[i-1]; } } f_max[n-1] = prices[n-1]; for (int i =n-2; i >=0 ; i--) { if (f_max[i+1]<prices[i]){ f_max[i] = prices[i]; }else { f_max[i] =f_max[i+1]; } } int res = 0; for (int i = 0; i <n ; i++) { int temp = f_max[i]-f_min[i]; res = Math.max(res,temp); } return res; } public int maxProfit(int[] prices) { int n = prices.length ; int[] f_min=new int[n+1]; // i 前面的包括i 最小值 是多少 int[] f_max = new int[n+1]; //i 以后的最大值 是多少 f_min[0] = prices[0]; for (int i = 1; i <n ; i++) { if (f_min[i-1]>prices[i]){ f_min[i] = prices[i]; }else { f_min[i]= f_min[i-1]; } } int res = 0; for (int i = 0; i <n ; i++) { int temp = prices[i]-f_min[i]; res = Math.max(res,temp); } return res; }

 

 

public int maxProfit(int[] prices) { int n = prices.length ; //手里只能持有 一只股票 只要是增序列 我就加 最长增序列 int[] f = new int[n]; // 1 表示 i+1 -1 > 0 的 for (int i = 0; i <n-1 ; i++) { if (prices[i+1]>=prices[i]){ f[i]=prices[i+1]-prices[i]; }else if (prices[i+1]<prices[i]){ f[i] = - 1; } } int res = 0; for (int i = 0; i <n-1 ; i++) { if (f[i]>=0){ res = res+f[i]; } } return res; } public int maxProfit(int[] prices) { int n = prices.length ; //手里只能持有 一只股票 只要是增序列 我就加 最长增序列 int res =0; for (int i = 0; i <n-1 ; i++) { if (prices[i+1]>=prices[i]){ res+=prices[i+1]-prices[i]; } } return res; }