柚子快报邀请码778899分享：Java：动态规划学习笔记
动态规划要点：
1.将复杂问题分解成简单子问题；
2.将重复性工作结果存储起来，下次碰到时查表解决。
动态规划适用范围：
1.最优子结构
简单来讲，母结构的最优解是所有子结构最优解的组合。
这和分治策略很像：（分治举例）体育场上，每个国家都会挑选他们国家最强的运动员、穿最先进的装备进入赛场，“选谁”“选什么装备”就是“如何赢得比赛”的这一问题的子问题，只要子问题能以最完美的方式解决，那么母问题就能以最完美的方式解决。
但在现实问题中，有很多子问题存在重叠的部分，这就用到了动态规划：（举例）挖金问题中，将是个金矿的人员分配分成两个子问题：
1.不挖第10个矿的情况下，给定挖矿人数，确定在前9个矿中挖取最多金子的方案；
2.挖第10个矿的情况下，给定挖矿人数，确定在前9个矿中挖取最多金子的方案；
得出两个子问题的最优方案后，就可以根据子问题的最优解以及第10个矿的信息确定整体最优解。（详细内容后面会介绍）
2. 重复子问题
不同的决策序列，到达某个相同的阶段时，可能会产生相同的状态。有时子问题是否会重复出现不好分析，也可将母问题和子问题本质上是一样的，只是输入参数不同作为依据。这意味着当程序进展到某一阶段后可以通过查表将时间复杂度高的递归算法变成线性查找，缩减计算量。
3 无后效性
子问题的解一旦确定，就不再改变，不受它之后包含它的更大问题的求解决策影响
动态规划基础问题分类：
斐波那契数列：
斐波那契数列定义：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0; F(1) = 1;
F(n) = F(n - 1) + F(n - 2)，其中(n > 1)
代码实现：
//三种斐波那契数列实现方法
// 递归法
public int fib(int N) {
if (N == 0 || N == 1) {
return N;
}
return fib(N - 1) + fib(N - 2);
}
// 数组法
public int fib(int N) {
assert N > -1;
if (N == 0 || N == 1) {
return N;
}
int [] arr = new int[N + 1];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i <= N; i++) {
arr [i] = arr[i-2] + arr[i-1];
}
return arr[N];
}
// 替换法
public int fib(int N) {
if (N == 0 || N == 1) {
return N;
}
int x = 0,y = 1,z = 1,i = 0,end = N-2;
while (i <= end) {
z = x + y;
x = y;
y = z;
i++;
}
return z;
}
//三者都能实现，区别仅在于开发效率和代码效率上
//递归速度最慢，数组和替换速度一样快，但是数组法的空间复杂度为线性O(n)，而替换法的空间复杂度为O(1);
爬楼梯：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
分析： 爬一层楼梯时，1种；
爬两层楼梯时，2种；
爬三层楼梯时，3种；
爬四层楼梯时，5种……
从数列分析可知，该数列符合斐波那契数列规律，即f(n) = f (n-1)+f(n-2);
由此可以实现简单代码：
class ClimbStairs{
public int climbStairs(int n){
int[] num = new int[n];
num[0] = 1;
num[1] = 2;
for(int i = 3; i < n; i++){
num[i] = num[i-1] + num[i-2];
}
return num[n-1]
}
}
假如一次性可以爬[1.m]次，那么最终次数又是多少呢？
分析：(n
爬两层楼梯时，2种；
爬三层楼梯时，4种；
爬四层楼梯时，7种……
爬m层=前项之和+1
如果直接观察规律感觉吃力。还可以这么理解：
n < m 时，例如 m = 5; n = 3，那么：
爬一层后爬两层：1
爬两层后爬一层：2
一次性爬三层：1 爬上三层的方案数最终结果为4
这里需要注意理解的是：假设一共要爬a层楼，爬k(k 最终实现： class ClimbStairs{ public int climbStairs(int n， int m){ int[] num = new int[n]; num[0] = 1; num[1] = 2; for(int i = 2; i < m; i++){ num[i] = num[i-1] + num[i-2] + 1; } for(int i = m; i < n; i++){ num[i] = num[i-1] + num[i-2]; } return num[n-1] } } 根据这个案例，我们还能拓展一下，正式进入动态规划。 最小花费爬楼梯： 一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯，从下标n-1或n-2进入顶楼 请计算并返回达到楼梯顶部的最低花费。 登上第i个阶梯的代价，是之前两个阶梯中的最小值加上登上第i个阶梯本身的代价，如是往复，直至最后对下标n-1和n-2的最优登梯方案进行比较，选择整体最优解。 思路跟之前是差不多的，只是把需要传递的数字从方案数量改为代价值： class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; for(int i = 0; i < n; i++){ if(i == 0 || i == 1){ continue; } if(cost[i-1] > cost[i-2]){ cost[i] += cost[i-2]; }else{ cost[i] += cost[i-1]; } } return (cost[n-1] <= cost[n-2]) ? cost[n-1] : cost[n-2]; } } 打家劫舍: 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 跟之前的分析差不多，假定我们要分析第 i 个房屋中的最大金额，i-1 的钱我们不能碰，i-2 中应该包含了其之前除 i-3 外所有房屋方案中的最大收益，而 i-3 处应该也包含了除 i-4 处以外的所有方案。这样一来只要对比 i-2 和 i-3 方案就可以得到到达 i 处的最佳收益方案。 代码： class Solution { public int rob(int[] nums) { int l = nums.length; if(l == 1)return nums[0]; if(l <= 2)return (nums[0]> nums[1])? nums[0]:nums[1]; if(l > 2)nums[2] += nums[0]; for (int i = 3 ; i < l;i++){ nums[i] = nums[i] + ((nums[i-2]> nums[i-3])? nums[i-2]:nums[i-3]); } return (nums[l-2]> nums[lh-1])? nums[l-2]:nums[l-1]; } } 删除并获得点数： 给你一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 这题本质上是打家劫舍的变形，只要将数字本身乘上出现次数即可； class Solution { public int deleteAndEarn(int[] nums) { int max = 0; int l = nums.length; 。//找到最大数 for(int i : nums){ if(max < i)max = i; } int earn[] = new int[max + 1]; //统计每个数字出现次数和分数 for(int i : nums){ earn[i] += i; } //打家劫舍部分 if(max == 0)return 0; if(max >= 2)earn[2] += earn[0]; for (int i = 3 ; i <= max;i++){ earn[i] = earn[i] + ((earn[i-2]> earn[i-3])? earn[i-2]:earn[i-3]); } return (earn[max]> earn[max-1])? earn[max]:earn[max-1]; } } 矩阵 棋盘路径数统计： 一个机器人位于一个 m x n 网格的左上角(start点) 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标end” ）。 问总共有多少条不同的路径？ start end 思路很简单，穷举就行： //递归法（运行超时） class Solution { public static int count = 0; class Solut { public static int uniquePaths(int m, int n) { int L = 0; int R = 0; if(m == 1 || n == 1)return 1; if(m > 1){ L = uniquePaths(m-1,n); } if(n > 1){ R = uniquePaths(m,n-1); } return L+R; } } } //数组法 class Solution { public int uniquePaths(int m, int n) { int[][] arr = new int[m][n]; for(int i = 0; i < m ; i++){ arr[i][0] = 1; } for(int j = 0; j < n ; j++){ arr[0][j] = 1; } for(int i = 1; i < m; i++){ for(int j = 1; j < n ; j++){ arr[i][j] = arr[i-1][j] + arr[i][j-1]; } } return arr[m-1][n-1]; } } 到此，递归法小号太大暂且不论，但数组法任然有优化的空间。可以发现，第 i 行 j 列的数据可以只用带有 i 参数的表达式进行表达，由此缩写为： class Solution { public int uniquePaths(int m, int n) { int[] arr = new int[m]; for(int i = 0; i < m ; i++){ arr[i] = 1; } for(int i = 1; i < n; i++){ for(int j = m-2; j >= 0 ; j--){ arr[j] += arr[j+1] ; } } return arr[0]; } } 当然，到这一步我们可基本看出了该问题内含的数学规律，距离终点m行n列的格子可以有种排列组合，即（m,n）格到终点需要执行m+n-2次向右或者向下移动的操作，而其中向下的操作有m-1次，在序列中可以组合出多种路径可能。基于此我们可以实现代码： class Solution { public int uniquePaths(int m, int n) { long top = 1; long bottom = 1 for (int x = n, y = 1; y < m; ++x, ++y) { top = top * x; bottom = bottom * y; } return (int) top/bottom; } } 最小路径和 一如既往的拓展，如果移动到每个格子需要不同的代价，那么起点到终点代价最小的路径是哪一条呢？ 111311132153311222463 其实代码思路和之前数组法几乎一样,只是改为取相邻格中的最小值，不多赘述： class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; for(int i = 1; i < m;i++){ grid[i][0] += grid[i-1][0]; } for(int j = 1; j < n;j++){ grid[0][j] += grid[0][j-1]; } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ grid[i][j] += (grid[i-1][j]>grid[i][j-1])?grid[i][j-1]:grid[i-1][j]; } } return grid[m-1][n-1]; } } 这里贴一个被优化的算法（转载自leetcode），消耗比我的算法小： class Solution { public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for(int i=1;i fun(grid, i, dp); } return dp[m-1][n-1]; } public void fun(int[][] grid, int layer, int[][] dp){ int m = grid.length, n = grid[0].length; int i,j; if(layer>=m){ i=m-1; } else { i = layer; } j=layer-i; while(i>=0&&j<=n-1){ if(i==0){ dp[i][j] = dp[i][j-1]+grid[i][j]; } else if(j==0){ dp[i][j] = dp[i-1][j]+grid[i][j]; } else { dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j]; } i--; j++; } } } 优化总结（待修改） 棋盘路径数统计（带障碍物）： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 1 和 0 来表示。 思路和之前不带障碍物的版本差不多，只是增加了障碍物的判断： class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int x = obstacleGrid.length; int y = obstacleGrid[0].length; int[] a = new int[obstacleGrid[0].length]; a[0] = 1; if(obstacleGrid[x-1][y-1] == 1)return 0; if(obstacleGrid[0][0] == 1)return 0; for (int i = 0; i < obstacleGrid.length; i++) { for (int j = 0; j < obstacleGrid[0].length; j++) { if (obstacleGrid[i][j] == 0) { if(i != 0){ if (obstacleGrid[i - 1][j] == 1) { a[j] = 0; } } if (j == 0) continue; if (obstacleGrid[i][j - 1] == 0 && j != 0) { a[j] += a[j - 1]; } } } } return a[a.length - 1]; } } 二叉树树的最小路径和（三角形最小路径和） 给定一个三角形 triangle ，找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 class Solution { public int minimumTotal(List int x = triangle.size(); int[] t = new int[x]; for(int i = x - 1; i >= 0;i--){ for(int j = 0; j < i + 1;j++){ if(i == x-1){ t[j] = triangle.get(i).get(j); continue; } t[j] = triangle.get(i).get(j) + Math.min(t[j],t[j+1]); } } return t[0]; } } 最优算法（来自力扣）： class Solution { public int minimumTotal(List int level=triangle.size(); return complexCompute(level-1,triangle,new int[level+1]); } public int complexCompute(int level,List if(level==-1){ return arr[0]; } List int l=tmp.size(); for(int i=0;i arr[i]=Math.min(arr[i]+tmp.get(i),arr[i+1]+tmp.get(i)); } return complexCompute(level-1,triangle,arr); } } 优化总结： 列表嵌套引用比较耗时，建议事先引用一次（表达待修改） 下降路径最小和 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。 我的代码： class Solution { public int minFallingPathSum(int[][] matrix) { int l = matrix.length; for (int i = l - 2; i >= 0; i--) { for (int j = 0; j < l; j++) { if (j == 0 ) { matrix[i][j] += min(matrix[i + 1][j], matrix[i + 1][j + 1]); } else if (j == l - 1) { matrix[i][j] += min(matrix[i + 1][j], matrix[i + 1][j - 1]); } else if(l > 2){ matrix[i][j] += min(matrix[i + 1][j], matrix[i + 1][j - 1], matrix[i + 1][j + 1]); } } } for(int i = 0; i < l ;i++){ matrix[0][0] = min(matrix[0][0],matrix[0][i]); } return matrix[0][0]; } public static int min(int a, int b) { if (a > b) return b; return a; } public static int min(int a,int b,int c){ if(a < b){ if(a < c)return a; return c; } if(b < c)return b; return c; } } 力扣代码最优解： class Solution { public static int minFallingPathSum(int[][] matrix) { int min = Integer.MAX_VALUE; int row = matrix.length; if (row == 1) return matrix[0][0]; for (int i = 1; i < row; i++) { rob(matrix, i, matrix[0].length); } for (int i = 0; i < matrix[0].length; i++) { min = Math.min(min, matrix[row - 1][i]); } return min; } public static void rob(int[][] matrix, int row, int col) { for (int j = 0; j < col; j++) { matrix[row][j] = matrix[row][j] + Math.min(getMax(matrix[row - 1], j - 1, col), Math.min(getMax(matrix[row - 1], j, col), getMax(matrix[row - 1], j + 1, col))); } } private static int getMax(int[] arr, int j, int len) { if (j < 0 || j >= len) { return Integer.MAX_VALUE; } return arr[j]; } } 最大正方形： 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 class Solution { public int maximalSquare(char[][] matrix) { int max = 0; for (int i = 0; i < matrix.length - max; i++) { for (int j = 0; j < matrix[0].length; j++) { max = Math.max(max,check(i,j,matrix)); } if(max == Math.max(matrix.length,matrix[0].length))break; } return max*max; } public int check(int x,int y,char[][] a){ boolean check = true; int count = 0; while(check){ if(x+count >= a.length || y+count >= a[0].length)break; for(int m = 0 ; m <= count;m++){ if(a[x+count][y+m] == '0'){ check = false;break; } } for(int m = 0 ; m <= count;m++){ if(a[x+m][y+count] == '0'){ check = false; break; } } if(check)count++; } return count; } } 力扣代码待看 class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0; int height = matrix.length; int width = matrix[0].length; int maxSide = 0; int[][] dp = new int[height + 1][width + 1]; for (int row = 0; row < height; row++) { for (int col = 0; col < width; col++) { if (matrix[row][col] == '1') { dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1; maxSide = Math.max(maxSide, dp[row + 1][col + 1]); } } } return maxSide * maxSide; } } 字符串 最长回文字： 给你一个字符串 s，找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 class Solution { public int longestPalindromeSubseq(String s) { int l = s.length(); if(s == null || l <= 2){ return l; } char[] c = s.toCharArray(); String result = ""; int spread = 0; for(int i = 0 ; i < l;i++){ if(i-spread < 0 || i+spread >= l)break; while( c[i+spread] == c[ i-spread ] ){ spread++; if(i-spread < 0 || i+spread >= l)break; } if(spread*2+1 > result.length()){ result = "" + c[i]; for(int j = 1; j < spread;j++){ result = c[i-j] + result + c[i+j]; } } spread = 0; if(i == l-1)break; while(c[i+spread + 1 ] == c[i-spread]){ spread++; if(i-spread < 0 || i+spread + 1>= l)break; } if(spread * 2 + 2 > result.length()){ result= ""; for(int j = 1; j < spread;j++){ result = c[i-j] + result + c[i+j]; } } spread = 0; } return result.length(); } } 中心扩散法是个不错的选择 class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 2) { return s; } char[] charArray = s.toCharArray(); int start = 0, end = 0; for (int i = 0; i < charArray.length; i++) { int len1 = centerSpread(charArray, i, i); int len2 = centerSpread(charArray, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } public int centerSpread(char[] charArray, int left, int right) { while(left >= 0 && right < charArray.length && charArray[left] == charArray[right]) { left--; right++; } return right - left - 1; } } 最长回文字序列： 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 思路：最初的思路还是嵌套，但很快发现栈溢出或者超出时间限制，故从新思考对象结构以及相关办法；这时如果学习部分算法空间换时间的算法，就能解决问题： 例如：s ="bbbab" 列出计算矩阵a,并先在a[i][i]上设置为1，对应 i 这个字符为回文中心的情况： 11111 随后依次对字符 i 和字符 j 进行比较，如果相等则其回文长度a(i,j) = a(i +1, j - 1) +2，这里a(i,j)代表字符串第 i 个字符到第 j 个字符之间最大回文字数： 123121121 如果发生不等的情况，那么这个（i，j）组合是不对最大回文数有影响的，只要在（i-1,j）和（i,j-1）二者之中取最大值，就能知道（i , j）区间内字符串的最大回文字数。按照这个思路就能填满表格，而表格中的最大值就是所求值。 123241222112121 代码实现： class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; char c1 = s.charAt(i); for (int j = i + 1; j < n; j++) { char c2 = s.charAt(j); if (c1 == c2) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } } 编辑距离： 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符删除一个字符替换一个字符 例：word1 = "horse", word2 = "ros" 思路：仿照上题，建立二维数组辅助解题： 012345123 根据分析，可以发现存在三种情况： i 之前没有word2中字符，a（i，j）=a（i-1，j）+1 i 等于word2中 j 之前的字符，且 i 之前有符合字符，a（i，j）=a（i，j - 1）+1 i 不等于word2中 j 之前的字符，且 i 之前有符合字符，且 i 不等于word2中第 j 个字符 ， a（i，j）=a（i - 1，j - 1）+1 i 等于word2中第 j 个字符 ，a（i，j）=a（i - 1，j - 1） 根据四种情况编写程序： class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); if (n * m == 0) { return n + m; } int[][] D = new int[n + 1][m + 1]; for (int i = 0; i < n + 1; i++) { D[i][0] = i; } for (int j = 0; j < m + 1; j++) { D[0][j] = j; } for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { int left = D[i - 1][j] + 1; int down = D[i][j - 1] + 1; int left_down = D[i - 1][j - 1]; if (word1.charAt(i - 1) != word2.charAt(j - 1)) { left_down += 1; } D[i][j] = Math.min(left, Math.min(down, left_down)); } } return D[n][m]; } } 两个字符串的最小ASCII删除和： 给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。 代码： class Solution { public int minimumDeleteSum(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); int[][] ans = new int[l1+1][l2+1]; for(int i = 1 ; i <= l1 ; i++){ ans[i][0] = ans[i-1][0] + s1.codePointAt(i - 1); } for(int j = 1; j <= l2 ; j++){ ans[0][j] = ans[0][j -1] + s2.codePointAt(j - 1); } for(int i = 1; i <= l1; i++){ int code1 = s1.codePointAt(i-1); for(int j = 1; j <= l2; j++){ int code2 = s2.codePointAt(j-1); if(s1.charAt(i-1) != s2.charAt(j-1)){ ans[i][j] = Math.min(ans[i-1][j]+code1,ans[i][j-1]+code2); //System.out.println("i"+i+"j"+j+" "+ans[i][j]); }else{ ans[i][j] = ans[i-1][j-1]; //System.out.println("exce i"+i+"j"+j+" "+ans[i][j]); } } } return ans[l1][l2]; } } 最长递增子序列 最长公共子序列 买卖股票 树 背包问题: 一维动态规划： 多维动态规划： 柚子快报邀请码778899分享：Java：动态规划学习笔记 相关链接
发表评论