[数据结构与算法]Lintcode 动态规划练习

109 · 数字三角形

public class Solution {
    public int minimumTotal(int[][] triangle) {
        int n = triangle.length;
        if (n == 0) return -1;
        
        for (int i = n - 2; i >= 0; i --) {
            for (int j = 0; j <= i; j ++) {
                triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        return triangle[0][0];
    }
}

114 · 不同的路径

public class Solution {
    public int uniquePaths(int m, int n) {
        int f[][] = new int[m + 1][n + 1];
        f[0][1] = 1;

        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m][n];
    }
}

115 · 不同的路径 II

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                else if (i == 0 && j == 0) obstacleGrid[i][j] = 1;
                else if (i == 0) obstacleGrid[i][j] = obstacleGrid[i][j - 1];
                else if (j == 0) obstacleGrid[i][j] = obstacleGrid[i - 1][j];
                else obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            }
        }

        return obstacleGrid[n - 1][m - 1];
    }
}

679 · 不同的路径 III

public class Solution {
    public int uniqueWeightedPaths(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        if (n == 0 || m == 0) return 0;        

        Set[][] f = new HashSet[n][m];

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                f[i][j] = new HashSet();
                if (i == 0 && j == 0) {
                    f[i][j].add(grid[i][j]);
                }
                else {
                    if (i != 0) {
                        for (Object num : f[i - 1][j]) {
                            f[i][j].add((int)num + grid[i][j]);
                        }
                    }
                    if (j != 0) {
                        for (Object num : f[i][j - 1]) {
                            f[i][j].add((int)num + grid[i][j]);
                        }
                    }
                }
            }
        }

        int ans = 0;
        for (Object num : f[n - 1][m - 1]) ans += (int)num;

        return ans;
    }
}

630 · 骑士的最短路径II

public class Solution {
     public int shortestPath2(boolean[][] grid) {
		int n = grid.length;
		int m = grid[0].length;
		if (n == 0 || m == 0) return -1;

		int f[][] = new int[n][m];
		int[] dx = {-2, -1, 1, 2};
		int[] dy = {-1, -2, -2, -1};	
		
	   	for (int j = 0; j < m; j ++) {		//从左到右
			for (int i = 0; i < n; i ++) {
				if (grid[i][j]) continue;	//有障碍物
				if (i == 0 && j == 0) {		//起点
					f[i][j] = 1;
					continue;
				}
			   	for (int k = 0; k < 4; k ++) {
					int x = i + dx[k];
					int y = j + dy[k];					
					
				   	if (x < 0 || y < 0 || x >= n || f[x][y] == 0) continue;
				   	if (f[i][j] == 0) f[i][j] = f[x][y] + 1;
					else f[i][j] = Math.min(f[i][j], f[x][y] + 1);
			   	}
		   	}
	   	}

	   	return f[n - 1][m - 1] - 1;
    }
}

116 · 跳跃游戏

• 动规

public class Solution {
    public boolean canJump(int[] A) {
        int n = A.length;
        if (n == 0) return true;

        boolean f[] = new boolean[n];
        f[0] = true;
        for (int i = 0; i < n; i ++) {
            if (f[i] == false) continue;
            for (int j = 1; j <= A[i]; j ++) {
                if (i + j < n) {
                    f[i + j] = true;
                }
            }
        }
        return f[n - 1];
    }
}

• 贪心

public class Solution {
    public boolean canJump(int[] A) {
        int n = A.length;
        if (n == 0) return true;

        int maxx = 0;          //能够到达的最远处
        for (int i = 0; i < n; i ++) {
            if (i <= maxx && i + A[i] > maxx) {
                maxx = i + A[i];
            }
        }
        return maxx >= n - 1;
    }
}

92 · 背包问题

• 二维数组

public class Solution {
    public int backPack(int m, int[] A) {
        int n = A.length;

        int f[][] = new int[n + 1][m + 1];  //前i件物品放入容量为j的背包，最多能装f[i][j]
        for (int i = 1; i <= n; i ++) {
            int t = A[i - 1];				//第i件物品的重量是A[i - 1]
            for (int j = 0; j <= m; j ++) {         
                if (t > j) f[i][j] = f[i - 1][j];
                else f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - t] + t);
            }
        }

        return f[n][m];
    }
}

• 一维数组

public class Solution {
    public int backPack(int m, int[] A) {
        int f[] = new int[m + 1];		//前i件物品放入容量为j的背包，最多能装f[j]
        for (int i = 1; i <= A.length; i ++) {
            int t = A[i - 1];			//第i件物品的重量是A[i - 1]
            for (int j = m; j >= t; j --) {      		
                f[j] = Math.max(f[j], f[j - t] + t);
            }
        }

        return f[m];
    }
}

• 一维 + 或运算

public class Solution {
    public int backPack(int m, int[] A) {
        int f[] = new int[m + 1];       //如果前i件物品可以装出j的容量，则f[j] = 1
        
        f[0] = 1;
        for (int i = 1; i <= A.length; i ++) {
            int t = A[i - 1];           //第i件物品的重量是A[i - 1]
            for (int j = m; j >= t; j --) {  
                f[j] |= f[j - t];
            }
        }

        int ans = 0;
        for (int i = m; i >= 0; i --) {
            if (f[i] == 1) {
                ans = i;
                break;
            }
        }
        return ans;
    }
}

724 · 最小划分

public class Solution {
    public int findMin(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i ++) sum += nums[i];

        int f[] = new int[sum + 1];
        for (int i = 1; i <= nums.length; i ++) {
            int t = 2 * nums[i - 1];
            for (int j = sum; j >= t; j --) {
                f[j] = Math.max(f[j], f[j - t] + t);
            }
        }
        return sum - f[sum];
    }
}