对于网格上的动态规划,如果f[i][j]只依赖于本行的f[i][x]和上一行的f[i-1][y],则可以采用滚动数组的方法压缩空间。
https://www.luogu.com.cn/problem/P1002
public class P1002 { public static void main(String[] args) { int[] hx = {1,2,2,1,-1,-2,-2,-1}; int[] hy = {-2,-1,1,2,2,1,-1,-2}; boolean[][] hourse = new boolean[30][30]; long [][] ans = new long [30][30]; int n,m,x,y; Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); x = in.nextInt(); y = in.nextInt(); n+=2; m+=2; x+=2; y+=2; hourse[x][y] = true; for(int i=0;i<8;i++){ hourse[x+hx[i]][y+hy[i]] = true; } ans[2][1] = 1; for(int i=2;i<=n;i++){ for(int j=2;j<=m;j++){ if(hourse[i][j]) continue; else ans[i][j] = ans[i][j-1] + ans[i-1][j]; } } System.out.print(ans[n][m]); } }
https://www.lintcode.com/problem/515/
public class P515 { /** * @param costs: n x 3 cost matrix * @return: An integer, the minimum cost to paint all houses */ public int minCost(int[][] costs) { // write your code here int n = costs.length; int[][] f = new int[n+1][3]; for(int i=1; i<=n; i++){ for(int j=0; j<3; j++){ f[i][j] = Integer.MAX_VALUE; for(int k=0; k<3; k++){ if(k==j){ continue; }else{ f[i][j] = Math.min(f[i-1][k]+costs[i-1][j], f[i][j]); } } } } int res = f[n][0]; if(res>f[n][1]) res = f[n][1]; if(res>f[n][2]) res = f[n][2]; return res; } }
从满足划分条件的最后一个片段开始考虑问题。
https://www.lintcode.com/problem/108/
如果段数不固定,则用f[i]表示前i个元素分段后的某种性质
public class P108 { /** * @param s: A string * @return: An integer */ public int minCut(String s) { // write your code here int n = s.length(); if(n == 0 || n == 1) return 0; boolean[][] isHw = new boolean[n][n]; int[] f = new int[n+1]; for(int i=0; i<n; i++){ int l,r; l = i; r = i+1; while(l>=0 && r<n && s.charAt(l)==s.charAt(r)){ isHw[l][r] = true; l--; r++; } r=l=i; while(l>=0 && r<n && s.charAt(l)==s.charAt(r)){ isHw[l][r] = true; l--; r++; } } for(int i=1; i<=n; i++){ f[i] = Integer.MAX_VALUE; for(int j=0; j<i; j++){ if(isHw[j][i-1]==true && f[j]+1 < f[i]){ f[i] = f[j]+1; } } } return f[n]-1; } }
当题目指定段数时,用f[i][j]表示前i个元素分段后的某种性质
https://www.lintcode.com/problem/437/
public class P437 { /** * @param pages: an array of integers * @param k: An integer * @return: an integer */ public int copyBooks(int[] pages, int k) { // write your code here int len = pages.length; if(len == 0) return 0; if(k > len) k = len; int[][] f = new int[k+1][len+1]; for(int i=1 ;i<=len; i++){ f[0][i] = Integer.MAX_VALUE; } for(int i=1; i<=k; i++){ for(int j=1; j<=len; j++){ f[i][j] = Integer.MAX_VALUE; int sum = 0; for(int n=j; n>=0; n--){ f[i][j] = Math.min(f[i][j], Math.max(f[i-1][n], sum)); if(n>0){ sum += pages[n-1]; } } } } return f[k][len]; } }