从今天开始，我们开启一个新的历程——动态规划，动态规划英文Dynamic Programming.这也就是我们所说的DP大法。动态规划求解的是最优问题，在求解过程中，我们通过求解最小问题的最优解来求得问题的最优解。
在动态规划的问题中，最重要的是两个方面：

  1.   1. 状态的定义
  2.   1. 状态转移方程

Leetcode题目分析

32. 最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 输入：s = “)()())”输出：4 解释：最长有效括号子串是 “()()”

思路:这道题的是求解最长有效括号字串的长度，我们可以定义dp[i]来表示以第i个字符结尾的串最大有效长度。下面需要分析寻找动态转移方程；
显然，如果s.charAt(i)=='('，那么dp[i]肯定等于 0。
当s.charAt(i)==')'的时候，有两种情况：

  1.   1. 当`s.charAt(i-1) == '('`的时候， 则 `dp[i] = dp[i-2] + 2`
  2.   1. 当`s.charAt(i-1) == ')'`我们需要找到前面与之匹配的 '(' ,如果`s[i]==s[i - dp[i-1]]`的时候，我们可以让`dp[i] = dp[i-1]+dp[i - dp[i-dp[i-1]-2]+2`,

image.png
代码:

  1. class Solution {
  2.     public int longestValidParentheses(String s) {
  3.         int length = s.length();
  4.         int[] dp = new int[length];
  5.         int result = 0;
  6.         for(int i = 1; i < length; i++){
  7.             if(s.charAt(i) == ')'){
  8.                 if(s.charAt(i-1) == '('){
  9.                     dp[i] = (i >= 2 ? dp[i-2] : 0 )  + 2;
  10.                 }else if(i - dp[i-1] >= 1 && s.charAt(i - dp[i-1] - 1) == '('){
  11.                     dp[i] = dp[i-1] + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0)  + 2; 
  12.                 }
  13.             } 
  14.             result = Math.max(result, dp[i]);
  15.         }
  16.         return result;
  17.     }
  18. }

877. 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

输入：[5,3,4,5]输出：true 解释： 亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

思路： 定义 f[l][r]为考虑区间 [l,r]，在双方都做最好选择的情况下，先手与后手的最大得分差值为多少。
那么 f[1][n]为考虑所有石子，先手与后手的得分差值：

  • f[1][n]>0，则先手必胜，返回 True
  • f[1][n]<0，则先手必败，返回 False

根据题意，我们可以取到左边和右边两个石子，那么就有两种情况：

  • 如果取到左边的石子，价值为pile[l], 那么本次取到之后，先手变成后手，所以我们可以推出piles[l-1] - f[l+1][r] ,（为什么是减呢，是因为本次的先手变成下一次后手，所以我们要用下一次后手减去前手的差在加上本次先手取到的石子数量）
  • 如果取到左边的石子，价值为pile[l], 那么本次取到之后，先手变成后手，所以我们可以推出piles[r-1]-f[l][r-1]

由因为双方都想赢，所以都会作出最优决策，因此需要取两者的最大值。

  1. class Solution {
  2.     public boolean stoneGame(int[] piles) {
  3.         int length = piles.length;
  4.         //定义dp为i到j的石子，当前人与另外一个人的差值
  5.         int[][] dp = new int[length][length];
  6.         //初始化dp数组
  7.         for(int i = 0 ; i < length; i++){
  8.             dp[i][i] = piles[i];
  9.         }
  10.         //转移方程
  11.         for(int i = length - 2; i >= 0 ; i--){
  12.             for(int j = i + 1; j < length; j++){
  13.                 dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
  14.             }
  15.         }
  16.         return dp[0][length-1] > 0;
  17.     }
  18. }

<br />