关于java:思维私塾动态规划

在刷剑指 offer 和 LeetCode 中发现，动静布局是经常出现的一类题目，那么接下来咱们就来仔细分析和总结下其中的套路。

动静布局（DP）说白了其实就是一种求解最优解的办法，是一种比拟非凡的分治思维，利用它能够对工夫复杂度进行优化，其次要是依据状态转移方程来进行求解。

其外部蕴含了次要的两种思维就是分治和贪婪。

总体来说动静布局题目的解题思路就四步：

状态示意
转移方程
初始状态
最终状态

上面咱们具体的阐明一下这四步，在刚开始的时候咱们须要构建一个存储数据的表格，个别应用数组居多，而后通过剖析题目找出存在的状态转移方程，即从上一个状态到下一个状态是如何变动的，而后依据题目设置咱们的初始值，而后依据状态转移方程反复计算，在此过程中利用到了后面积攒下来的记录，所以可能加快速度。最初始终倒找最终咱们所须要的状态。

咱们这边拿剑指 offer 中的第 47 题礼物的最大价值这个典型的题目来举例让大家明确这个算法的思路

题目：

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有肯定的价值（价值大于 0）。你能够从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下挪动一格、直到达到棋盘的右下角。给定一个棋盘及其下面的礼物的价值，请计算你最多能拿到多少价值的礼物？

解法

本文说了是解说动静布局的必定是要用动静布局来解决这个问题。那咱们就依照咱们的步骤来进行

状态示意

设动静布局矩阵 dp[][]，其中 dpi 示意从棋盘的左上角开始达到单元格 (i,j) 时能拿到礼物的最大累计价值

转移方程

因为只能向右或者向下挪动，所以：

- 当 i = 0 且 j =0，为起始元素
- 当 i = 0 且 j≠0，为第一行元素，只能右边达到
- 当 i≠0 且 j =0，为第一列元素，只能上边达到
- 当 i≠0 且 j 不等于 0，可从上边或者右边达到

所以，状态转移方程如下所示：

初始状态

从下面剖析咱们能够晓得 dp0=grid0

最终状态

最终状态就是咱们遍历完即 dpm-1。返回 dp 数组中右下角的元素

java 实现

有了思路前面就是 java 的实现，如下所示：

class Solution {public int maxValue(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        //dp[i][j]示意从 grid[0][0]到 grid[i - 1][j - 1]时的最大价值
        int[][] dp = new int[row + 1][column + 1];
        for (int i = 1; i <= row; i++) {for (int j = 1; j <= column; j++) {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][column];
    }
}

这些就是动静布局的所有内容了，作为一个在 LeetCode 中和面试中都经常出现的题目，能够说是必须要把握起来了。总之就是关注四件事件：

状态示意
转移方程
初始状态
最终状态

其中最难的就是转移方程，这个要依据各个题目灵活处理，或者多做一些题目总结也能够取得不错的播种和提高。只有有了状态转移方程，前面的初始状态和边界值再多加留神就没有什么大问题了。

如果感觉看完有播种，心愿能关注一下，顺便给我点个赞，这将会是我更新的最大能源，感激各位的反对
欢送各位关注我的公众号【java 冢狐】，专一于 java 和计算机基础知识，保障让你看完有所播种，不信你打我
求一键三连：点赞、转发、在看。
如果看完有不同的意见或者倡议，欢送多多评论一起交换。感激各位的反对以及厚爱。

——我是冢狐，和你一样酷爱编程。

欢送关注公众号“Java 冢狐”，获取最新消息

关于java:思维私塾动态规划

介绍

解题思路

真题演练

间断子数组的最大和

题目：

解法

java 实现

总结

最初