算法之动态规划(一)

动态规划

动态规划题目的特征
1.重叠子问题（Overlapping Subproblems）：这意味着在递归算法中，相同的子问题被多次求解。动态规划通过存储子问题的解，避免了重复计算，从而提高效率。
2.最优子结构（Optimal Substructure）：一个问题的最优解包含其子问题的最优解。这意味着，如果我们能够找到每个子问题的最优解，我们就能构建出整个问题的最优解。

步骤：

1.定义状态：
确定dp数组的含义，dp[i]通常表示某个状态的值，例如，到达第i天的最大金子数量、到达第i个节点的最短路径长度等。
2.确定状态转移方程：
根据问题的特点，找出状态之间的关系，即如何从一个或多个已知状态推导出新的状态值。
3.确定初始状态和边界条件：
设置dp数组的初始值，这通常是问题的基本情形，例如，dp[0] = 0。
4.确定遍历顺序：
根据问题的特点，确定是自顶向下还是自底向上的遍历顺序，以及如何更新dp数组。
5.填充dp数组：
根据状态转移方程，按照确定的遍历顺序填充dp数组。
6.构造最优解：
根据dp数组的结果，构造问题的最优解。
通常结合记忆化搜索减少动态规划的时间复杂度！！！ 记忆化的数组有一个条件是不能和数组初始化的数值一样不然容易造成混淆！！！

70. 爬楼梯

首先写出递归出口当i<=1时，只有一种方案
这里的memo数组是起到记忆化搜索的功能，防止重复计算
dp[i]=dp[i-1]+dp[i-2];
加入memo数组的话递归的子结构函数：memo[i]=dfs(i-1,memo)+dfs(i-2,memo)

class Solution {
    public int climbStairs(int n) {
        int[] memo=new int[n+1];
        return dfs(n,memo);
    }
    int dfs(int i,int[] memo){
        if(i<=1)return 1;
        if(memo[i]!=0)return memo[i];
        return memo[i]=dfs(i-1,memo)+dfs(i-2,memo);
    }
}

198. 打家劫舍

和上一题的解法一样

class Solution {
    private int[] nums,memo;
    public int rob(int[] nums) {
        this.nums=nums;
        int n=nums.length;
        memo=new int[n];
        Arrays.fill(memo,-1);
        return dfs(n-1);
    }
    private int dfs(int i) {
        if (i < 0) { // 递归边界（没有房子）
            return 0;
        }
        if (memo[i] != -1) { // 之前计算过
            return memo[i];
        }
        int res=Math.max(dfs(i-1),dfs(i-2)+nums[i]);
        return memo[i]=res;
    }
}

2320. 统计放置房子的方式数

只算一侧，算完一侧之后相乘就算两侧的房子个数

class Solution {
    public int countHousePlacements(int n) {
        final int MOD = 1000000007;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
        return (int) ((long) dp[n] * dp[n] % MOD);
    }
}

LCR 166. 珠宝的最高价值

首先定义一个状态数组dp[i][j]
状态方程: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + frame[i][j];当前网格线的值等于左侧或上侧的最大值最后加上当前网格线的值
边界条件：只有一行dp[i][0] = dp[i-1][0] + frame[i][0];
只有一列：dp[0][j] = dp[0][j-1] + frame[0][j];

class Solution {
    public int jewelleryValue(int[][] frame) {
         int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = frame[0][0];
        for(int i=1; i<m; i++){
            dp[i][0] = dp[i-1][0] + frame[i][0];
        }
        for(int j=1; j<n; j++){
            dp[0][j] = dp[0][j-1] + frame[0][j];
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + frame[i][j];
            }
        }
        return dp[m-1][n-1]; 
    }
}

63. 不同路径 II

容易想到状态转移方程：dp[i][j] =dp[i - 1][j] +dp[i][j - 1];（只有当前网格不是钻石的时候）
边界条件：只有一行dp[i][j] = dp[i][j - 1];只有一列：dp[i][j] =dp[i - 1][j];

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=obstacleGrid[0][0]==1?0:1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (obstacleGrid[i][j] != 1) {
                    if (i > 0 && j > 0) {
                        dp[i][j] =dp[i - 1][j] +dp[i][j - 1];
                    } else if (i > 0) {
                        dp[i][j] =dp[i - 1][j];
                    } else if (j > 0) {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
        }
        return dp[m-1][n-1];
    }
}