代码随想录算法训练营第三十三天| 62.不同路径 、63. 不同路径 II、343. 整数拆分 。c++转java

62.不同路径

思路：按照dp五步法分析，成功AC。代码随想录

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for(int i = 1 ;i <= m ;i++){
            for(int j = 1;j <= n ;j++){
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
}

63. 不同路径 II

思路：这道题跟前面的题很相似，就是有一个小坑的地方，就是如果只有一行的情况，本来想用第一题代码随想录中提到的初始化第一行和第一列都为1，显然在这里就是不适用的，就还是沿用了我自己写的第一题初始化的方法，只管第一个节点。(或者当对第一行或者第一列初始化的时候，遇到障碍就停止)

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //排除掉起点就有障碍的情况
        if(obstacleGrid[0][0] == 1)
            return 0;
        int m = obstacleGrid.length,n = obstacleGrid[0].length;
        int[][] dg = new int[m + 1][n + 1];
        dg[0][1] = 1;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(obstacleGrid[i - 1][j - 1] == 1)
                    continue;
                dg[i][j] = dg[i - 1][j] + dg[i][j - 1];
            }
        }
        return dg[m][n];
    }
}

343. 整数拆分

思路：动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili

先看视频。使用五步法

1.题目求的是n的最大化乘积，所以有dp[i]就是i的最大乘积。

2.递推公式：dp[i] = max(dp[i],j * dp[i - j],j * (i - j)).

3.遍历顺序：3~n.

4.初始化：dp[2] = 1.

5.举例

至于这里为什么递推公式是这样的，俺的理解就是，题目是要将n进行拆分，所以是先从拆两个数开始，然后往下拆分，所以先比较的是j * (i - j),如果需要接着往下拆分的话，需要先确定j，然后i求(i-j)能够被拆分的最大乘积，至于这里为什么要确定j，主要是因为如果也拆成dp[j],就没有考虑到拆分成三个数的情况，如果理解有误，请佬佬指点~。

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n;i++){
            for(int j = 1;j <= i/2;j++){
                dp[i] = Math.max(dp[i],Math.max(j * (i - j),j * dp[i - j]));
            }
        }
        return dp[n];
    }
}