动态规划学习总结day2
day 2
坐标型动态规划
unique-paths-ii
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
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-1>=0) f[i][j]+=f[i-1][j];
if(j-1>=0) f[i][j]+=f[i][j-1];
}
}
}
}
return f[m-1][n-1];
}
}
序列型动态规划
Paint House
public class Solution {
/**
* @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 m = costs.length;
if(m==0) return 0;
int n = costs[0].length;
int [][] f = new int[m+1][n];
f[0][0]= f[0][1]=f[0][2] = 0;
for(int i =1;i<=m;i++){
for(int j =0;j<n;j++){
f[i][j]=Integer.MAX_VALUE;
for( int k = 0;k<n;++k){
if(k==j)continue;
else{
if(f[i-1][k]+costs[i-1][j]<f[i][j]){
f[i][j]=f[i-1][k]+costs[i-1][j];
}
}
}
}
}
int res = f[m][0];
if(f[m][1]<res) res = f[m][1];
if(f[m][2]<res) res = f[m][2];
return res;
}
}
划分型动态规划
class Solution {
public int numDecodings(String ss) {
char [] s = ss.toCharArray();
int n = s.length;
if(n==0)return 0;
int []f = new int[n+1];
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];
}
}
坐标型动态规划升级联系
longest-continuous-increasing-subsequence
class Solution {
public int findLengthOfLCIS(int[] a) {
int n =a.length;
int[] f = new int[n];
int res = 0;
for(int i =0;i<n;++i){
f[i]=1;
if(i>0&&a[i-1]<a[i])f[i]+=f[i-1];
res = Math.max(res,f[i]);
}
return res;
}
}
class Solution {
public int findLengthOfLCIS(int[] a) {
int n =a.length;
int[] f = new int[2];
int old,now =0;
int res = 0;
for(int i =0;i<n;++i){
old = now;
now = 1-old;
f[now] = 1;
if(i>0&&a[i-1]<a[i])f[now]+=f[old];
res = Math.max(res,f[now]);
}
return res;
}
}
minimum-path-sum
class Solution {
public int minPathSum(int[][] grid) {
if(grid==null||grid.length==0||grid[0].length==0) return 0;
int m = grid.length;
int n = grid[0].length;
int[][] f = new int[2][n];
int old ,now = 0;
int t1,t2;
for(int i =0;i<m;++i){
old = now;
now = 1-old;
for(int j = 0;j<n;j++ ){
if(i==0&&j==0){
f[now][j] = grid[i][j];
continue;
}
f[now][j]=grid[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];
}
}
炸弹袭击
counting-bits
class Solution {
public int[] countBits(int num) {
int n =num;
int [] f = new int[n+1];
f[0]=0;
for(int i =1;i<=n;++i){
f[i] = f[i>>1]+(i%2);
}
return f;
}
}