LeetCode动态规划

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

public static int climbStairsDp(int n){
    int []dp=new int[n+1];
    dp[0]=1;
    dp[1]=1;
    for (int i=2;i<=n;i++) {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

//  Max[i]=max(nums[i-2]+nums[i],nums[i-1])
public int rob(int[] nums) {
    if(nums==null || nums.length<=0) return 0;
    int[] dp=new int[nums.length];
    dp[0]=nums[0];
    for(int i=1;i<nums.length;i++){
        dp[i]=Math.max(i>=2?dp[i-2]+nums[i]:nums[i],dp[i-1]);
    }
    return dp[nums.length-1];
}

// Max[i]=max(pre+nums[i],cur);  
public int rob(int[] nums) {
    if(nums==null||nums.length<=0){
        return 0;
    }
    int pre= 0; //前一天
    int cur= 0; //当天，其实就是为了保存前后两天的 dp[i]
    for (int i=0;i<nums.length;i++) {
        int temp=cur;
        cur=Math.max(pre+nums[i],cur);
        //向后走
        pre=temp;
    }
    return cur;
}

输入：[2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

输入：[1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

public int rob(int [] nums){
    if(nums==null||nums.length<=0){
        return 0;
    }
    if(nums.length==1){
        return nums[0];
    }
    if(nums.length==2){
        return Math.max(nums[0],nums[1]);
    }
    int n=nums.length;
    return Math.max(rob(nums,1,n),rob(nums,0,n-1));
}

public int rob(int[] nums,int start,int end) {
    int pre=0; //前一家最大值
    int cur=0; //当前最大值
    for (int i=start;i<end;i++) {
        int temp=cur;
        cur=Math.max(pre+nums[i],cur);
        pre=temp;
    }
    return cur;
}

输入：
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

public int minPathSum(int[][] grid) {
    int[][] dp=new int[grid.length][grid[0].length];
    for (int i=0;i<grid.length;i++) {
        for (int j=0;j<grid[0].length;j++) {
            //第一行
            if(i==0 && j!=0){
                dp[i][j]=grid[i][j]+dp[i][j-1];
            }else if(i!=0 && j==0){
                dp[i][j]=grid[i][j]+dp[i-1][j];
            }else if(i!=0 && j!=0){
                dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
            }else{
                dp[i][j]=grid[i][j];
            }
        }
    }
    return dp[grid.length-1][grid[0].length-1];
}

func minPathSum(grid [][]int) int {
    var m = len(grid)
    var n = len(grid[0])
    var dp = make([][]int, m)
    for i := 0; i < m; i++{
        dp[i] = make([]int, n)
    }
    dp[0][0] = grid[0][0]
    for i := 1; i < m; i++{
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    for j := 1; j < n; j++{
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    for i := 1; i < m; i++{
        for j := 1; j < n; j++{
            dp[i][j] = grid[i][j] + Min(dp[i-1][j], dp[i][j-1])
        }
    }
    return dp[m-1][n-1]
}

func Min(a, b int) int{
    if a > b{
        return b
    }
    return a
}

import java.util.*;
import java.io.*;
//https://projecteuler.net/problem=82  answer:260324
public class PathSum_threeWays_projecteuler{
    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new FileReader("/usr/p082_matrix.txt"));
        int index = 0;
        int m = 80, n = 80;
        int[][] matrix = new int[m][n];
        while (index < 80) {
            String[] line = reader.readLine().split(",");
            for (int j = 0; j < 80; j++) {
                matrix[index][j] = Integer.valueOf(line[j]);
            }
            index++;
        }
        int INF = 0x3f3f3f3f;
        int[][] dp = new int[m][n];
        for (int j = 0; j < m; j++) {
            dp[j][0] = matrix[j][0];
        }
        for (int j = 1; j < m; j++) {
            //首先只考虑向右走和向下走
            for (int i = 0; i < m; i++) {
                if (i==0){ //第一行，只能从左边转移
                    dp[i][j] = matrix[i][j] + dp[i][j-1];
                }else{ //从左边或者上边转移
                    dp[i][j] = matrix[i][j] + Math.min(dp[i][j-1], dp[i-1][j]);
                }
            }
            for (int i = m-1; i >= 0; i--) {
                //三目写的太长看着挺不舒服。..
                //dp[i][j] = i==m-1?dp[i][j]:Math.min(dp[i][j], matrix[i][j]+dp[i+1][j]);
                if (i<m-1) { //从下面转移和从上/左面转移的最小值
                    dp[i][j] = Math.min(dp[i][j], matrix[i][j]+dp[i+1][j]);
                }
                //最后一行，只能从左边或者上面转移，也是就是第一个循环的值
                //dp[i][j] = dp[i][j]
            }
        }
        int res = INF;
        for (int i = 0; i < m; i++) {
            res = Math.min(res, dp[i][m-1]);
        }
        System.out.println(res);
    }
}

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

输入：m = 7, n = 3
输出：28

public int uniquePaths(int m, int n) {
    if(m<0||n<0){
        return 0;
    }
    int[][] dp=new int[n][m];
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if(i==0&&j!=0){
                dp[i][j]=1;
            }else if(j==0 && i!=0){
                dp[i][j]=1;
            }else if(j!=0&&i!=0){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }else{
                dp[i][j]=1;
            }
        }
    }
    return dp[n-1][m-1];
}

public static int uniquePaths2(int m, int n) {
    if(m<0||n<0){
        return 0;
    }
    int[] dp=new int[n]; 
    Arrays.fill(dp,1); //第一行，第一列均为 1
    for (int i=1;i<m;i++) { //一行一行向下走
        for (int j=1;j<n;j++) {
            //这里的 dp[j] 和 dp[j-1] 分别就代表了 上边 和 左边的元素
            dp[j]=dp[j]+dp[j-1]; //求每一行每个元素的 dp 值
        }
    }
    return dp[n-1]; //最后一行最后一个 dp 值就是结果
}

public int uniquePaths(int m, int n) {
    if(m<0||n<0){
        return 0;
    }
    int step=m+n-2;
    int down=n-1;
    long res=1;
    for (int i=1;i<=down;i++) {
        res=res*(step-down+i)/i; //递推
    }
    return (int)res;
}

输入：
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

//dfs 回溯 , TLE
private int[][] direction={{0,1},{1,0}};

private int count=0;

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid==null || obstacleGrid.length<=0 || obstacleGrid[0][0]==1) {
        return 0;
    }
    boolean[][] visit=new boolean[obstacleGrid.length][obstacleGrid[0].length];
    dfs(obstacleGrid,visit,0,0);
    return count;
}

public void dfs(int[][] obstacleGrid,boolean[][] visit,int x,int y) {
    //!=1 是为了 coner case
    if (x==obstacleGrid.length-1 && y==obstacleGrid[0].length-1 && obstacleGrid[x][y]!=1) {
        count++;
        return;
    }
    for (int i=0;i<direction.length;i++) {
        int nx=x+direction[i][0];
        int ny=y+direction[i][1];
        if (nx<obstacleGrid.length && ny<obstacleGrid[0].length && !visit[nx][ny] && obstacleGrid[nx][ny] !=1) {
            visit[nx][ny]=true;
            dfs(obstacleGrid,visit,nx,ny);
            visit[nx][ny]=false;
        }
    }
}

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid==null || obstacleGrid.length<=0 || obstacleGrid[0][0]==1) {
        return 0;
    }
    int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];
    for (int i=0;i<obstacleGrid.length;i++) {
        for (int j=0; j<obstacleGrid[0].length;j++) {
            if (obstacleGrid[i][j]==1) {
                dp[i][j]=0;
            }else if (i==0 && j==0) {
                dp[0][0]=1;
            }else if(i==0 && j!=0){
                dp[0][j]=dp[0][j-1];
            }else if (j==0 && i!=0) {
                dp[i][0]=dp[i-1][0];
            }else{
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }
    return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
}

//一维 dp
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid==null || obstacleGrid.length<=0 || obstacleGrid[0][0]==1) {
        return 0;
    }
    //以行为单位向下走
    int[] dp=new int[obstacleGrid[0].length];
    dp[0]=1;
    for (int i=0;i<obstacleGrid.length;i++) {
        for (int j=0; j<obstacleGrid[0].length;j++) {
            if (obstacleGrid[i][j]==1) {
                dp[j]=0;
            }else if(i==0 && j!=0){ //第一行
                dp[j]=dp[j-1];
            }else if(i!=0 && j!=0){ 
                dp[j]=dp[j]+dp[j-1];
            }
            //每一行第一列的 dp[j]=dp[j], 和上一行的第一列保持一致就行
        }
    }
    return dp[obstacleGrid[0].length-1];
}

func uniquePathsWithObstacles(grid [][]int) int {
    var m = len(grid)
    var n = len(grid[0])
    var dp = make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }
    dp[0][1] = 1 //初始值
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if grid[i-1][j-1] != 1 {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m][n]
}

输入：m = 2, n = 2, N = 2, i = 0, j = 0
输出：6
解释：

输入：m = 1, n = 3, N = 3, i = 0, j = 1
输出：12
解释：

int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};

int mod=(int)1e9+7;

Long[][][] dp=null;

public int findPaths(int m, int n, int N, int i, int j) {
    dp=new Long[m][n][N+1];
    return (int)(dfs(m,n,i,j,N)%mod);
}

public long dfs(int m,int n,int x,int y,int k){
    if(k==0) return 0;
    if(dp[x][y][k]!=null){
        return dp[x][y][k];
    }
    long count=0;
    for(int i=0;i<dir.length;i++){
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(!valid(m,n,nx,ny)){
            count++;
            continue;
        }
        count=(count+dfs(m,n,nx,ny,k-1))%mod;
    }
    return dp[x][y][k]=(count)%mod;
}

public boolean valid(int m,int n,int x,int y){
    return x>=0 && x<m && y>=0 && y<n;
}

//自底向上递推
public int findPaths(int m, int n, int N, int i, int j) {
    int mod=(int)1e9+7;
    //群里偷学到的
    int[] dir={0,1,0,-1,0};
    long[][][] dp=new long[m][n][N+1];
    for (int k=1;k<=N;k++) { //想想 K 为什么在最外层
        for (int r=0;r<m;r++) {
            for (int c=0;c<n;c++) {
                for (int d=0;d<4;d++) {
                    int nx=r+dir[d];
                    int ny=c+dir[d+1];
                    if(nx<0 || ny<0 || nx>=m ||ny>=n){
                        dp[r][c][k]++;
                    }else{
                        dp[r][c][k]=(dp[r][c][k]+dp[nx][ny][k-1])%mod;
                    }
                }
                //提前结束，只需要 i,j,N 就行了（貌似没有快多少）
                if(k==N && r==i && c==j){
                    return (int)(dp[i][j][N]);
                }
            }
        }
    }
    //return (int)(dp[m-1][n-1][N]); md 一开始返回错了，看了半天
    return 0;
}

输入：3, 2, 0, 0
输出：0.0625
解释：
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第 2 步均有且只有 2 种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。

//小数据可以过，大数据过不了
//K[0,100] 直接 8^100 就爆了，所以肯定不能像上面那样求，dp 得存概率
public double knightProbability(int N, int K, int r, int c) {
    int[][] dir={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
    int[][][] dp=new int[N][N][K+1];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            //这题如果反着求出界路径就错了，得正向求
            dp[i][j][0]=1; 
        }
    }
    for(int k=1;k<=K;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                for(int d=0;d<dir.length;d++){
                    int nx=i+dir[d][0];
                    int ny=j+dir[d][1];
                    if(nx>=0 && nx<N && ny>=0 && ny<N){
                        dp[i][j][k]+=(dp[nx][ny][k-1]);
                    }
                }
            }
        }
    }
    return dp[r][c][K]/Math.pow(8,K);
}

//DP 存概率 AC 解法
public double knightProbability(int N, int K, int r, int c) {
    int[][] dir={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
    double[][][] dp=new double[N][N][K+1];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp[i][j][0]=1;
        }
    }
    for(int k=1;k<=K;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                for(int d=0;d<dir.length;d++){
                    int nx=i+dir[d][0];
                    int ny=j+dir[d][1];
                    if(nx>=0 && nx<N && ny>=0 && ny<N){
                        //md，一开始不知道为啥想到求独立事件 P(A U B) 上去了
                        //但是其实两者并不是独立事件，是互斥事件直接 P(A)+P(B) 就行了
                        dp[i][j][k]+=(dp[nx][ny][k-1])/8;
                    }
                }
                //提前返回
                if(i==r && j==c && k==K){
                    return dp[i][j][k];
                }
            }
        }
    }
    return dp[r][c][K];
}

//自顶向上
Double[][][] dp=null;

int[][] dir={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};

public double knightProbability(int N, int K, int r, int c) {
    dp=new Double[N][N][K+1];
    return dfs(N,K,r,c);
}

public double dfs(int N,int k,int x,int y){
    if(k==0) return 1.0;
    if(dp[x][y][k]!=null){
        return dp[x][y][k];
    }
    double p=0;
    for (int i=0;i<dir.length;i++) {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>=0 && nx<N && ny>=0 && ny<N){
            p+=dfs(N,k-1,nx,ny)/8;
        }
    }
    return dp[x][y][k]=p;
}

输入：1
输出：10

输入：2
输出：20

输入：3
输出：46

int[][] dir={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};

int mod=(int)1e9+7;

Integer[][][] dp=null;

public int knightDialer(int N) {
    int[][] grid={{1,2,3},{4,5,6},{7,8,9},{-1,0,-1}};
    int res=0;
    dp=new Integer[4][3][N];
    for(int i=0;i<grid.length;i++){
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]!=-1){
                res=(res+dfs(grid,i,j,N-1))%mod;
            }
        }
    }
    return res;
}

public int dfs(int[][] grid,int x,int y,int N){
    if(N==0) return 1;
    if(dp[x][y][N]!=null) return dp[x][y][N];
    int res=0; //一开始赋值成 1 了。从当前位置起跳，所以当前位置不应该有初始值
    for(int i=0;i<dir.length;i++){
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(valid(grid,nx,ny)){
            res=(res+dfs(grid,nx,ny,N-1))%mod;
        }
    }
    return dp[x][y][N]=res;
}

public boolean valid(int[][] grid,int x,int y){
    return x>=0 && y>=0 && x<grid.length && y<grid[0].length && grid[x][y]!=-1;
}

int mod=(int)1e9+7;

Integer[][] dp=null;

public int knightDialer(int N) {
    //直接看图建立对应关系
    int[][] next={{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{0,1,7},{2,6},{1,3},{2,4}};
    int res=0;
    dp=new Integer[10][N];
    for(int i=0;i<=9;i++){
        res=(res+dfs(i,N-1,next))%mod;
    }
    return res;
}

public int dfs(int num,int N,int[][] next){
    if(N==0) return 1;
    if(dp[num][N]!=null) return dp[num][N];
    int res=0; //注意别写成 1 了
    for(int i=0;i<next[num].length;i++){
        res=(res+dfs(next[num][i],N-1,next))%mod;
    }
    return dp[num][N]=res;
}