>1.最大子序和问题 //找到整数数组nums的具有最大和的连续子数组(子数组最少包含一个元素)并返回其最大和 public int maxSubArray(int[] nums) { //动态规划思路: //dp[i]代表从数组的开始位置到下标为i的和的最大值 //dp[i] = Math.max(dp[i - 1], dp[i - 1] + nums[i]) //上一行即判断:每一次dp[i]的时候要不要加上前面的i-1个(即dp[i-1]有没有可能是负的) //针对nums = {-2,1,-3,4,-1,2,1,-5,4}来说 //nums[i] -2 1 -3 4 -1 2 1 -5 4 //dp[i] -2 1 -2 4 3 5 6 1 5 //res MIN 1 1 4 4 5 6 6 6 int[] dp = new int[nums.length]; dp[0] = nums[0]; int res = Integer.MIN_VALUE; for(int i = 1; i < nums.length; i++) { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); res = Math.max(res, dp[i]); } return Math.max(res,dp[0]); } >2.爬楼梯问题 //共n阶台阶,每次可走1阶或2阶,问有多少种走法 public int climbStairs(int n) { //定义dp[i]为走到第i阶的路径数,由于每一步可走1阶或2阶 //显然dp[i]与dp[i - 1]、dp[i - 2]有关,转移方程如下: //dp[i] = dp[i - 1] + dp[i - 2] if (n == 1) return 1; if (n == 2) return 2; int[] dp = new int[n + 1];//dp[0] = 0可省略不写 dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; // return n == 1 ? 1 : (n == 2 ? 2 : (climbStairs(n - 1) + climbStairs(n - 2))); //上面一行的递归方法时间复杂度比动态规划高!!超时!!!! } //思考:如果每一步可走1阶、2阶或3阶,又将会有多少种走法呢? public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i <= n; i++) { dp[i] = dp[i- 1] + dp[i - 2] + dp[i - 3]; } return dp[n]; } >2.1类似问题还有:leetcode.62 不同路径问题: leetcode.62:从一个m*n的网格的左上角走到右下角,一共有多少种走法(规定每次只能向下或向右走) class Solution { public int uniquePaths(int m, int n) { if (m == 1 || n == 1) return 1; //return uniquePaths(m, n - 1) + uniquePaths(m - 1, n);//直接递归,运行超时!!! int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][0] = dp[0][j] = 0; dp[i][1] = dp[i][j] = 1; dp[i][j] = dp[i][j - 1] + dp[i - 1][j]; } } return dp[m][n]; } }