线性规划概念
动态规划的主要特点是状态的推导是按照问题规模 i ii 从小到大依次推过去的（或者从后往前一直推过来的,比如「石子游戏」、「2140.解决智力问题」就是从后往前推的)，较大规模的问题的解依赖较小规模的问题的解。
通常做此类问题步骤如下：
LeetCode 877. 石子游戏
class Solution { public boolean stoneGame(int[] piles) { int n = piles.length; long[][] dp = new long[n + 1][n + 1]; // dp[i][j]代表从区间[i,j]之间获得的最多分数 // dp[i][j] = Math.max(piles[i] + dp[i + 1][j], dp[i][j - 1] + plies[j]) // dp[i][i] = 0 // dp[0][n - 1] > 0 ? true : false; for (int i = 0 ; i < n; i++) { dp[i][i] = 0; } for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { dp[i][j] = Math.max(piles[i] + dp[i + 1][j], dp[i][j - 1] + piles[j]); } } return dp[0][n - 1] > 0 ? true : false; } }
LeetCode 2140. 解决智力问题
class Solution { public long mostPoints(int[][] q) { int n = q.length; // dp[i]的含义是从下标i~n-1获取的最大分数值 // dp[i] = Math.max(dp[Math.min(n, q[i][1])] + q[i][0], dp[i]) long[] dp = new long[n + 1]; for (int i = n - 1; i >= 0; i--) { dp[i] = Math.max(dp[Math.min(n, i + q[i][1] + 1)] + q[i][0], dp[i + 1]); } return dp[0]; } }
LeetCode 72. 编辑距离
class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); // 含义：dp[i][j]代表Word1从下标0~i和word2从下标0~j所使用的的最少操作次数 // 状态转移方程：dp[i][j] = Math.min(dp[i -1][j] + 1,Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + (word1.charAt(i - 1) != word2.charAt(j - 1) ? 1 : 0))); int[][] dp = new int[n + 1][m + 1]; if (n * m == 0) { return n + m; } for (int i = 0; i <= n; i++) { dp[i][0] = i; } for (int j = 0 ; j <= m ; j++) { dp[0][j] = j; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int left = dp[i -1][j] + 1; int down = dp[i][j - 1] + 1; int left_down = dp[i - 1][j - 1]; if (word1.charAt(i - 1) != word2.charAt(j - 1)) { left_down++; } dp[i][j] = Math.min(left_down, Math.min(left, down)); } } return dp[n][m]; } }
