2022-07-11 动态规划

剑指 Offer II 100. 三角形中最小路径之和

优化路径，建立表达式子 dp[i+1][j]=Math.min(dp[i][j]+tmp1,dp[i+1][j]);
dp[i+1][j+1]=Math.min(dp[i][j]+tmp2,dp[i+1][j+1]);

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {

        // 动态规划
        int m=triangle.size();int n=triangle.get(m-1).size();

        int[][] dp=new int[m][n];

        for(int i=0;i<m;i++){
           
            for(int j=0;j<n;j++){
     dp[i][j]=Integer.MAX_VALUE;
            }
        }

        dp[0][0]=triangle.get(0).get(0);
        for(int i=0;i<m-1;i++){
           
            for(int j=0;j<i+1;j++){
                int tmp1=triangle.get(i+1).get(j);
                int tmp2=triangle.get(i+1).get(j+1);
              dp[i+1][j]=Math.min(dp[i][j]+tmp1,dp[i+1][j]);
             dp[i+1][j+1]=Math.min(dp[i][j]+tmp2,dp[i+1][j+1]);     
        }
        }

        int min=dp[m-1][0];
        for(int i=0;i<m;i++){
            // System.out.println(dp[m-1][i]);
         min=Math.min(dp[m-1][i],min);
        }
        return min;


    }
}




#### [剑指 Offer II 103\. 最少的硬币数目](https://leetcode.cn/problems/gaM7Ch/)
把amount进行划分，建立dp数组，数组的下标对应硬币的个数，动态规划方程
dp[i]=Math.min(dp[i-coins[j]+1,dp[i]),
初始dp[0]=0,其余数值是amount+1,
最后进行判定能否dp[amout]>amount?amount:dp[amount];

class Solution {
public int coinChange(int[] coins, int amount) {

    int n=coins.length;
    Arrays.sort(coins);
    if(amount==0){
        return 0;
    }
    

    int[] dp=new int[amount+1];
    Arrays.fill(dp,amount+1);
    dp[0]=0;
    for(int i=1;i<amount+1;i++){
        for(int j=n-1;j>=0;j--){
            if(coins[j]<=i){
           dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
            }
        }
    }
    return dp[amount]>amount?-1:dp[amount];
    

}

}

剑指 Offer II 104. 排列的数目

和上面的一样，拆分成背包，然后构造动态规划方程。
dp[i]+=dp[i-num];

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 动态规划和深度优先遍历
        Arrays.sort(nums);

        int  n=nums.length;
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<target+1;i++){
            for(int num:nums){
                if(i>=num){
                  dp[i]+=dp[i-num];
                }
             
            }

        }
        return dp[target];

    }
}

剑指 Offer II 107. 矩阵中的距离

对于矩阵中的任意一个 11 以及一个 00，我们如何从这个 11 到达 00 并且距离最短呢？根据上面的做法，我们可以从 11 开始，先在水平方向移动，直到与 00 在同一列，随后再在竖直方向上移动，直到到达 00 的位置。这样一来，从一个固定的 11 走到任意一个 00，在距离最短的前提下可能有四种方法：
只有 水平向左移动 和 竖直向上移动；

只有 水平向左移动 和 竖直向下移动；

只有 水平向右移动 和 竖直向上移动；

只有 水平向右移动 和 竖直向下移动。

动态规划+深度遍历

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;
         int[][] dp=new int[m][n];
         for(int i=0;i<m;i++){
       Arrays.fill(dp[i],Integer.MAX_VALUE/2);
         }


        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                dp[i][j]=0;
                }
                if(i+1<m){
               dp[i+1][j]=Math.min(dp[i][j]+1,dp[i+1][j]);
                }
                if(j+1<n){
                    dp[i][j+1]=Math.min(dp[i][j]+1,dp[i][j+1]);
                }
            }
        }
         for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(mat[i][j]==0){
                dp[i][j]=0;
                }
                if(i-1>=0){
               dp[i-1][j]=Math.min(dp[i][j]+1,dp[i-1][j]);
                }
                if(j-1>=0){
                    dp[i][j-1]=Math.min(dp[i][j]+1,dp[i][j-1]);
                }
            }
        }
        return dp;


    }
}

剑指 Offer 60. n个骰子的点数

这个关键是确定前一次和后一次筛子的数组要配置好。

class Solution {
    public double[] dicesProbability(int n) {
        double[] dp=new double[6];
        Arrays.fill(dp,1.0/6.0);

        int left=n;
    //  

    for(int i=2;i<=n;i++){

    double[] tmp=new double[5*i+1];
    for(int j=0;j<dp.length;j++){
        for(int k=0;k<6;k++){
       tmp[j+k]+=dp[j]/6;
        }
    }
    dp=tmp;
    }
    return dp;
    }
}