算法九 动态规划(Java实现)
动态规划概述
动态规划(dynamic programming)是运筹字的一一个分支,是求解决策过程最优化的数学方法。它是20世纪50年代初美国数学家R.E.Bellman等人提出的最优化原理,它利用各阶段之间的关系,逐个求解,最终求得全局最优解。在设计动态规划算法时需要确认原问题与子问题、动态规划状态、边界状态结值、状态转移方程等关键要素。
动态规划原理
(以第一题为例)
1.确认原问题与子问题:原问题为求n阶台阶所有走法的数量,子题是求1阶台阶、2阶台阶、... n-1阶台阶的走法。
2.确认状态:本题的动态规划状态单一,第i个状态即为i阶台阶的所有走法数量。
3.确认边界状态的值:边界状态为1阶台阶与2阶台阶的走法,1阶台阶有1种走法,2阶台阶有2种走法,即dp[1]= 1,dp[2]= 2。
4.确定状态转移方程:将求第i个状态的值转移为求第i-1个状态值与第i-2个状态的值,动态规划转移方程,dp[i] = dp[i-1] + dp[i-2]; (i>=3)。
1、LeetCode70爬楼梯
思路:1.设置递推数组d[0..n],dp[i]代表到达第i阶,有多少种走法,初始化数组元素为0。
2.设置到达第1阶台阶,有1种走法;到达第2阶台阶,有2种走法。
3.利用i循环递推从第3阶至第n阶结果:到达第i阶的方式数量=到达第i-1阶的方式数量+到达第i-2阶的方式数量
class Solution { public int climbStairs(int n) { int[] dp = new int[n + 2]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } } 复制代码
2、LeetCode198打家劫舍
思路:1.确认原问题与子问题: 原问题为求n个房间的最优解,子问题为求前1个房间、前2个房间、..前n-1个房间的最优解。
2.确认状态:第i个状态即为前i个房间能够获得的最大财宝(最优解)。
3.确认边界状态的值: 前1个房间的最优解,第1个房间的财宝;前2个房间的最优解,第1、2个房间中较大财宝的。
4.确定状态转移方程:a.选择第1个房间:第i个房间+前i-2个房间的最优解。
b.不选择第i个房间:前i- 1个房间的最优解。
动态规划转移方程:dp[i] = max(dp[i-1], dp[i-2] + nums[i]);(i>= =3)。
class Solution { public int rob(int[] nums) { if (nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } //设第i个房间的最优解为dp[i] int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]); } return dp[nums.length -1]; } } 复制代码
3、LeetCode53最大子序和
思路:将求n个数的数组的最大子段和,转换为分别求出以第1个、第2个、...第i个、...第n个数字结尾的最大字段和,再找出这n个结果中最大的,即为结果。
动态规划算法:第i个状态(dp[i])即为以第i个数字结尾的最大子段和(最优解)。由于以第i-1个数字结尾的最大子段和(dp[i-1])与nums[i]相邻:若dp[i-1] > 0:dp[i] = dp[i-1] + nums[i];否则:dp[i] = nums[i];边界值:以第1个数字结尾的最大字段和dp[0] = nums[0]。
class Solution { public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(nums[i], dp[i] = dp[i -1] + nums[i]); if (dp[i] > max) { max = dp[i]; } } return max; } } 复制代码
4、LeetCode322零钱兑换
思路:钞票面值:coins=[1,2,5, 7,10] ;金额: 14;dp[i],代表金额的最优解(即最小使用张数);数组dp[]中存储金额1至金额14的最优解(最少使用钞票的数量)。在计算dp[i]时,dp[0]、 dp[1]、 dp[2]、 .. dp[i-1]都是已知的。而金额可由:金额i-1与coins[0] (1)组合;金额i-2与coins[1] (2)组合;金额i-5与coins[2] (5)组合;金额i-7与coins[3] (7)组合;金额i-10与coins[4] (10)组合;即状态i可由状态i-1、i-2、 i-5、 i-7、 i-10,5个状态所转移到,故dp[i] = min(dp[i-1], dp[i-2], dp[i-5], dp[i-7], dp[i-10])+ 1。
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; //初始化dp数组,最初所有金额的最优解均为-1(不可达到) Arrays.fill(dp, -1); //金额0的最优解是0 dp[0] = 0; //获得从1到i之间所有的最优解,从而推出i的最优解 for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (i - coins[j] >= 0 && dp[i - coins[j]] != -1) { if(dp[i] == -1 || dp[i] > dp[i - coins[j]]+1){ dp[i] = dp[i - coins[j]] + 1; } } } } return dp[amount]; } } 复制代码
5、LeetCode120三角形最小路径和
思路:1.设置一个二维数组,最优值三角形dp[] [], 并初始化数组元素为0。dp[i] [j]代表了从底向上递推时,走到三角形第i行第j列的最优解。
2.从三角形的底面向三角形上方进行动态规划。a.动态规划边界条件:底面上的最优值即为数字三角形的最后一层。b.利用i循环,从倒数第二层递推至第一层,对于每层的各列,进行动态规划递推:第i行,第j列的最优解为dp[i] [j],可 到达(i,j)的两个位置的最优解dp[i+1] [j]、dp[i+1] [j+1]:dp[i] [j] = min(dp[i+1] [j], dp[i+1] [j+1]) + triangle[i] [j] 。
3.返回dp[0] [0]。
class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[][] dp = new int[n + 1][n + 1]; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j); } } return dp[0][0]; } } 复制代码
6、LeetCode300最长递增子序列
设置动态规划数组dp[],第i个状态dp[i]代表以第i个元素结尾的最长上升子序列的长度;动态规划边界:dp[0]= 1;初始化最长上升子序列的长度LIS= 1;从1到n-1,循环i,计算dp[i];从0至i-1,循环j,若nums[i]> nums[j],说明nums[i]可放置在nums[j]的后面,组成最长上升子序列;若dp[i] <dp[j] + 1:dp[i]= dp[i]+ 1,LIS为dp[0],dp[1],...dp[i]... ,dp[n-1]中最大的。
class Solution { public int lengthOfLIS(int[] nums) { int len = nums.length; if (len == 1) { return 1; } int[] dp = new int[len]; Arrays.fill(dp, 1); int LIS = 0; for (int i = 1; i < len; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j] && dp[i]<dp[j] + 1) { dp[i] = Math.max(dp[i], dp[j] + 1); } } LIS = Math.max(LIS, dp[i]); } return LIS; } } 复制代码
7、LeetCode64最小路径和
官方思路:创建二维数组dp,与原始网格的大小相同,dp[i] [j] 表示从左上角出发到 (i,j)位置的最小路径和。显然dp[0] [0]=grid[0] [0]。对于dp 中的其余元素,通过以下状态转移方程计算元素值。
当 i>0 且 j=0 时,dp[i] [0]=dp[i-1] [0]+grid[i] [0]。
当 i=0 且 j>0 时,dp[0] [j]=dp[0] [j-1]+grid[0] [j]。
当 i>0 且 j>0 时,dp[i] [j]=min(dp[i-1] [j],dp[i] [j-1])+grid[i] [j]。
最后得到dp[m-1] [n-1]的值即为从网格左上角到网格右下角的最小路径和。
class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int rows = grid.length, columns = grid[0].length; int[][] dp = new int[rows][columns]; dp[0][0] = grid[0][0]; for (int i = 1; i < rows; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int j = 1; j < columns; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (int i = 1; i < rows; i++) { for (int j = 1; j < columns; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[rows - 1][columns - 1]; } } 复制代码
8、LeetCode174地下城游戏
思路:从右下向左上递推:dp[i] [j]即代表若要达到右下角,至少有多少血量,能在行走的过程中至少保持生命值为1。
若代表地牢的二维数组为1* n或n* 1的:1* n,i从n-2至0:dp[0] [i] = max(1, dp[0] [i+1]- dungeon[0] [i]);n* 1, i从n-2至0:dp[i] [0] = max(1, dp[i+1] [0]- dungeon[i] [0])。
若代表地牢的二维数组为n* m的:i代表行,从n-2至0;j代表列,从m-2至0;设dp_ min = min(dp[i+ 1] [j], dp[i] [j+ 1]);dp[i] [j] = max(1, dp_ min - dungeon[i] [j])。
class Solution { public int calculateMinimumHP(int[][] dungeon) { int row = dungeon.length; int column = dungeon[0].length; int[][] dp = new int[row][column]; dp[row-1][column-1]=Math.max(1, 1-dungeon[row-1][column-1]); for (int i = column -2; i >= 0; i--) { dp[row-1][i] = Math.max(1,dp[row-1][i+1]-dungeon[row-1][i]); } for (int i = row -2; i >= 0; i--) { dp[i][column-1] = Math.max(1,dp[i+1][column-1]-dungeon[i][column-1]); } for (int i = row -2; i >= 0; i--) { for (int j = column -2; j >= 0; j--) { int dp_min = Math.min(dp[i+1][j], dp[i][j+1]); dp[i][j] = Math.max(1, dp_min-dungeon[i][j]); } } return dp[0][0]; } }
作者:zust_Isabella
链接:https://juejin.cn/post/7013641653563064351