Loading... # 动态规划 ## 动态规划题目特点   ## 解题步骤 1. 确定状态 找出 `f(x-i)、f(x-i)(x-j)` 也就是子问题 2. 转移方程 `f[x]=f[x-i]+n、f[x][y]=f[x][y-j]+f[x-i][y]` 3. 初始条件和边界情况 ## 例题 例题1： 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-change 题解： ```java class Solution { public int coinChange(int[] coins, int amount) { int length = coins.length; int[] f = new int[amount+1]; f[0] = 0; int sum=0; for(int i=1;i<=amount;++i){ f[i]=Integer.MAX_VALUE; //选择硬币 即为 f[x-1] f[x-2]... for(int j=0;j<length;++j){ if(i>=coins[j]&&f[i-coins[j]]!=Integer.MAX_VALUE&&f[i-coins[j]]+1<f[i]){ f[i] = f[i-coins[j]]+1; } } } if(f[amount]!=Integer.MAX_VALUE){ return f[amount]; } return -1; } } ``` 例题2： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths 题解： ```java class Solution { public int uniquePaths(int m, int n) { 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]=1;//边界情况 }else{ //否则就是 上面 左边 走到 f[i][j] f[i][j] = f[i-1][j]+f[i][j-1]; } } } return f[m-1][n-1]; } } ``` 例题3： 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/jump-game/ 题解： ```java class Solution { public boolean canJump(int[] nums) { if(nums==null||nums.length==0){ return false; } // // v1 动态规划 // int length = nums.length; // boolean[] f = new boolean[length]; // f[0]=true;//初始化 // for(int j=1;j<length;j++){ // //最后一步 // f[j]=false;//先设置为false // //枚举石头 ，只要有一个能够满足距离小于nums[i] 即为 nums[i]>=j-i => i+nums[i]>=j // for(int i=0;i<j;i++){ // if(f[i]&&i+nums[i]>=j){ // f[j]=true; // break;//因为只要有一个就行 // } // } // } // return f[length-1]; // v2 贪心算法 int max_length=0; // 最大能到达的距离 for(int i=0;i<nums.length;i++){ if(i<=max_length){ // 判断能不能到达 i 这个点 max_length=Math.max(i+nums[i],max_length); // 更新最大步长 if(max_length>=(nums.length-1)){ // 如果最大步长直接能到最后一个点就直接返回 true return true; } } } return false; } } ``` 例题4： 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/ 题解： ```java class Solution { public int maxSubArray(int[] nums) { //v1 // int length=nums.length; // int[] f=new int[length+1]; // //最大字串必须包含 nums[i] // f[0]=nums[0]; //初始状态，以nums[0] 结尾 // //思路 // // f[length] 最大数组长度 // // f[i] 和最大值 以nums[i]为结尾 // // f[i-1] <=0 负贡献 执行 f[i]=nums[i] // // f[i-1] >0 正贡献 执行 f[i]=nums[i]+f[i-1] // int res = nums[0]; //返回结果，即为 f[] 中最大值 // for(int i=1;i<length;i++){ // if(f[i-1] <= 0){ // f[i]=nums[i]; // }else{ // f[i]=nums[i]+f[i-1]; // } // if(f[i]>res){ // res=f[i]; // } // } // return res; //v2 优化空间复杂度 int res=nums[0]; for(int i=1;i<nums.length;i++){ nums[i]+=Math.max(nums[i-1],0); res=Math.max(res,nums[i]); } return res; } } ``` ## 总结  Last modification：December 10th, 2020 at 01:46 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
