算法通关村第十九关 | 青铜 | 动态规划

2023-12-13 10:32:47

1.统计路径总数(递归)

原题:力扣62.

每次移动都是将问题规模缩小。

要理解:return search(m - 1, n) + search(m, n - 1);

public class Solution {
    public int uniquePaths (int m, int n) {
        return search(m, n);
    }
    public int search(int m, int n) {
        // 就剩一行或一列,只有一条路径,递归结束
        if (m == 1 || n == 1) {
            return 1;
        }
        // 分解为两个更小的矩阵之和
        return search(m - 1, n) + search(m, n - 1);
    }
}

2.使用二维数组优化递归(记忆化搜索)

原题:力扣62.

相同大小的矩阵已经计算过了,就不需要再计算了,这个是记忆化搜索。

public int uniquePaths(int m, int n) {
	int[][] f = new int[m][n];
    f[0][0] = 1;
    // 这里直接循环遍历,因为前边的都算过了
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
        	if (i > 0 && j > 0) {
            	f[i][j] = f[i - 1][j] + f[i][j - 1];
        	} else if (i > 0) {
            	f[i][j] = f[i - 1][j];
        	} else if (j > 0) {
            	f[i][j] = f[i][j - 1];
        	}
        } 
    }
    return f[m - 1][n - 1];
}

3.滚动数组(一维数组代替二维数组)

原题:力扣62.

滚动数组:反复更新数组。

这样的写法包括了重复子问题,记忆化搜索,滚动数组,是一个简单的动态规划。

公式:dp[j] = dp[j] + dp[j - 1]

public int uniquePaths(int m, int n) {
	int[] dp = new int[n];
    Arrays.fill(dp, 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];
        }
    }
    return dp[n - 1];
}

4.最小路径和(拓展)

原题:力扣64.

状态转移方程:f[i][j] = min{f[i-1][j],f[i][j-1]} + A[i][j]

public int minPathSum(int[][] grid) {
	int m = grid.length, n = grid[0].length;
    int[][] f = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) {
                f[i][j] = grid[i][j];
            } else {
                int top = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
                int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                f[i][j] = Math.min(top, left);
            }
        }
    }
    return f[m - 1][n - 1];
}

5.三角形最小路径和(拓展)

原题:力扣120.

可以用无后效性来分析是否可以使用动态规划,如果当前状态确定后,之后的状态转移与之前的决策无关,那么就可以使用动态规划。

public int minimumTotal(List<List<Integer>> tri) {
	int n = tri.size();
    int ans = Integer.MAX_VALUE;
    int[][] f = new int[n][n];
    f[0][0] = tri.get(0).get(0);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            int val = tri.get(i).get(j);
            f[i][j] = Integer.MAX_VALUE;
            if (j != 0) {
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + val);
            }
            if (j != i) {
                f[i][j] = Math.min(f[i][j], f[i - 1][j] + val);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, f[n - 1][i];
    }
    return ans;
}

如果对您有帮助,请点赞关注支持我,谢谢! ?
如有错误或者不足之处,敬请指正! ?
个人主页:星不易 ?
算法通关村专栏:不易|算法通关村 ?

文章来源:https://blog.csdn.net/m0_57130776/article/details/134947084
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。