DP的特点
无后效性：未来与过去无关。即：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前的各状态的影响。
最优子结构：大问题的最优解 可以由小问题的最优解 推出
DP的操作过程 将一个大问题转化为几个小问题，大事化小，小事化了：
DP经典题型
但是感觉不管查什么资料都是这些，其实什么也解决不了，根据做题的经验，动态规划最难的地方，一是确定一道题能不能用动态规划解决，二就是怎么确定状态，就是f(n)怎么定义。
线性表： length – length + 1
字符串（线性表）–> 前缀 + 后缀 –> 前缀 true && 后缀 true –> true
dp[i] 表示以 i 结尾的子段和的最大值
1 2 3 4 5 6 7 8 public int maxSubArray (int [] nums) int [] dp = new int [nums.length]; dp[0 ] = nums[0 ]; for (int i=1 ;i<nums.length;i++) dp[i] = Math.max(nums[i], dp[i-1 ]+nums[i]); Arrays.sort(dp); return dp[dp.length-1 ]; }
这道题就是字符串的问题，并且是前缀 + 后缀问题
dp[i] : 字符串 s[:i] 能否能否由字典中的词拆分开。（以i结尾的字符串能否被字典拆分开）求 dp[i] : 如果 dp[j]=true, 并且 s[j:i] 在字典中，那么 dp[i] 为 true
1 2 3 4 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words , determine if s can be segmented into a space -separated sequence of one or more dictionary words . Note: 1. The same word in the dictionary may be reused multiple times in the segmentation.2. You may assume the dictionary does not contain duplicate words .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static boolean wordBreak (String s, List<String> wordDict) boolean [] dp = new boolean [s.length()+1 ]; dp[0 ] = true ; for (int i=1 ;i<=s.length();i++) { for (int j=0 ;j<i;j++) { String tmp = s.substring(j, i); if (dp[j]&&wordDict.contains(tmp)) { dp[i] = true ; break ; } } } return dp[s.length()]; }
输入：[10, 9, 2, 5, 3, 7, 101, 18]，则输出为：4，因为最长的上升子序列是：[2, 3, 7, 101]
dp[i]: 以第i位为结尾的最长上升子序列的长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int lengthOfLIS (int [] nums) if (nums.length==0 ) return 0 ; int [] dp = new int [nums.length]; for (int i=0 ;i<nums.length;i++) { dp[i] = 1 ; for (int j=i-1 ;j>=0 ;j--) { if (nums[j]<nums[i]) dp[i] = Math.max(dp[j]+1 , dp[i]); } } Arrays.sort(dp); return dp[nums.length-1 ]; }
输入：text1= “abcde” , text2 = “ace”
输出：3
最长公共子序列不需要连续，只要是共同有的就行了。
最长公共子串是需要连续的。
1 2 3 4 5 6 7 8 9 10 11 12 public int longestCommonSubsequence (String text1, String text2) int [][] dp = new int [text1.length()+1 ][text2.length()+1 ]; for (int i=1 ;i<=text1.length();i++) { for (int j=1 ;j<=text2.length();j++) { if (text1.charAt(i-1 )==text2.charAt(j-1 )) dp[i][j] = dp[i-1 ][j-1 ]+1 ; else dp[i][j] = Math.max(dp[i-1 ][j], dp[i][j-1 ]); } } return dp[text1.length()][text2.length()]; }
dp[m][n] 表示走到 m n 位置时的走法数dp[m][n] = dp[m-1][n] + dp[m][n-1]相似题目：leetcode 63. 62题多了障碍 ，就是递归的时候多了判断而已。
1 2 3 4 5 6 7 8 9 10 11 12 public int uniquePaths (int m, int n) int [][] dp = new int [m][n]; for (int i=0 ;i<m;i++) dp[i][0 ] = 1 ; for (int i=0 ;i<n;i++) dp[0 ][i] = 1 ; for (int i=1 ;i<m;i++) for (int j=1 ;j<n;j++) dp[i][j] = dp[i-1 ][j] + dp[i][j-1 ]; return dp[m-1 ][n-1 ]; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public static int canCompleteCircuit (int [] gas, int [] cost) int res_index = 0 ; for (int i=0 ;i<gas.length;i++) { if (gas[i]<cost[i]) continue ; else { boolean flag = true ; int [] dp = new int [2 *gas.length]; dp[i] = gas[i] - cost[i]; for (int j=i%gas.length+1 ;j<2 *gas.length;j++) { dp[j] = dp[j-1 ]+gas[j%gas.length]-cost[j%gas.length]; if (dp[j]<0 ) { flag = false ; break ; } } if (flag) { res_index = i; return res_index; } } } return -1 ; }
1 2 3 4 5 6 7 8 9 10 Input: 3 Output: 5 Explanation: Given n = 3 , there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
要分析有多少独一无二的二叉搜索树的个数。那么可以定义f(x):x为根节点时二叉搜索树的个数
f(x)的定义很关键。。看到这个定义我就知道怎么做了。但是自己想的时候就想不到这一点。😭
当n为根节点时，那么其他1…n-1都在其左子树。那么f(n)=n-1个节点能够成的二叉搜索树的个数。
当n-1为根节点时，那么其他1…n-2都在其左子树，右子树只有n，那么f(n-1)=n-2个节点能够组成的二叉搜索树的个数*右子树只有一个节点能组成的二叉搜索树的个数。
所以可以定义G(x): 1…x能够组成的二叉搜索树的个数。
1 2 3 4 5 6 7 f (n )=G (n -1 )*G (0 )f (n -1 ) = G (n -2 )*G (1 )f (n -2 ) = G (n -3 )*G (2 )... f(1 ) = G (0 )*G (n -1 ) 而 f (1 )+f (2 )+...+f (n ) = G (n ) 所以：G (n ) = G (n -1 )*G (0 ) + G (n -2 )*G (1 ) + G (n -3 )*G (2 ) + ... + G (0 )*G (n -1 )
从上面我们就能看出来，要想求G(n), 要先求出 G(0)…G(n-1)
G(0) = 1, G(1) = 1;
G(2) = G(1)*G(0) + G(0)*G(1) = 2
G(3) = G(2)*G(0) + G(1)*G(1) + G(0)*G(2)
1 2 3 4 5 6 7 8 9 10 public int numTrees (int n) int [] dp = new int [n+1 ]; dp[0 ] = 1 ; dp[1 ] = 1 ; for (int i=2 ;i<=n;i++) for (int j=i-1 ;j>=0 ;j--) dp[i] += dp[j]*dp[i-j-1 ]; return dp[n]; }
虽然感觉是在96的基础上做了变形，但是完全不一样啊！！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public List<TreeNode> generateTrees1 (int n) if (n <= 0 ) return new ArrayList<>(); List<TreeNode> list = greateSubTree(1 , n); return list; } private List<TreeNode> greateSubTree (int start, int end) List<TreeNode> res = new ArrayList<>(); if (end < start) { res.add(null ); return res; } for (int i = start; i <= end; i++) { for (TreeNode l : greateSubTree(start, i-1 )) { for (TreeNode r : greateSubTree(i+1 , end)) { TreeNode root = new TreeNode(i); root.left = l; root.right = r; res.add(root); } } } return res; }
1 2 3 4 5 6 [ | index: [2], | 0 [3,4], | 0 1 [6,5,7], | 0 1 2 [4,1,8,3] | 0 1 2 3 ] | 0 1 2 3 4
从下到上，第 n 行第 i 个位置 由第 n-1 行的第 i-1个和第 i 个走到，取两个路径和中小的那个。
dp[n][i] = nums[n][i] + min(dp[n-1][i-1], dp[n-1][i])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int minimumTotal (List<List<Integer>> triangle) int result = Integer.MAX_VALUE; int m = triangle.size(); int n = triangle.get(m-1 ).size(); int [][] dp = new int [m][n]; dp[0 ][0 ] = triangle.get(0 ).get(0 ); for (int i=1 ;i<m;i++) { int size = triangle.get(i).size(); dp[i][0 ] = dp[i-1 ][0 ] + triangle.get(i).get(0 ); dp[i][size-1 ] = dp[i-1 ][size-2 ] + triangle.get(i).get(size-1 ); for (int j=1 ;j<triangle.get(i).size()-1 ;j++) dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i-1 ][j-1 ], dp[i-1 ][j]); } for (int i=0 ;i<n;i++) result = dp[m-1 ][i] < result ? dp[m-1 ][i] : result; return result; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public boolean isSubsequence (String s, String t) if (s.length()==0 ) return true ; else if (s.length()>t.length()) return false ; boolean [][] dp = new boolean [s.length()][t.length()]; dp[0 ][0 ] = (s.charAt(0 )==t.charAt(0 )); for (int i=1 ;i<t.length();i++) dp[0 ][i] = (s.charAt(0 )==t.charAt(i) || dp[0 ][i-1 ]); for (int i=1 ;i<s.length();i++) { for (int j=i;j<t.length();j++) { dp[i][j] = (s.charAt(i)==t.charAt(j)&&dp[i-1 ][j-1 ]) || dp[i][j-1 ]; } } return dp[s.length()-1 ][t.length()-1 ]; }
每2的幂开始，就是前面全部的位置+1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …….
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 …….
4的位置，8的位置，16的位置开始，都是从头部遍历，然后+1即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public int [] countBits(int num) { int [] dp = new int [num+1 ]; if (num>=0 ) dp[0 ] = 0 ; if (num>=1 ) dp[1 ] = 1 ; if (num>=2 ) dp[2 ] = 1 ; if (num>=3 ) dp[3 ] = 2 ; if (num<=3 ) return dp; int i=4 ; int tmp = 2 ; while (i<=num) { int cou = 0 ; int start = (int )Math.pow(2 , tmp); int end = (int )Math.pow(2 , tmp+1 ); int j = start; while (j<end && j<=num) { dp[j] = dp[cou] + 1 ; j += 1 ; cou += 1 ; } i = j; tmp += 1 ; } return dp; }
1 2 3 4 5 6 7 8 Input: prices = [1 , 3 , 2 , 8 , 4 , 9 ], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0 ] = 1 Selling at prices[3 ] = 8 Buying at prices[4 ] = 4 Selling at prices[5 ] = 9 The total profit is ((8 - 1 ) - 2) + ((9 - 4 ) - 2) = 8.
股票必须先卖出然后才能再买入。
hold[i]：表示第 i 时刻手里有股票的最大收益。那么该状态可由两种情况得到。一种是之前没有股票，在该时刻买入。一种是之前就有股票：hold[i] = max(hold[i-1], unhold[i-1]-prices[i])unhold[i]：表示第 i 时刻手里没有股票最大收益。一种是之前有股票，在该时刻卖出。一种是之前就没有股票： unhold[i] = max(unhold[i-1], hold[i-1]+prices[i]-fee)最终返回 unhold[len-1]。即最后时刻手里没有股票。
1 2 3 4 5 6 7 8 9 10 public int maxProfit (int [] prices, int fee) int [] hold = new int [prices.length]; int [] unhold = new int [prices.length]; hold[0 ] = 0 -prices[0 ]; for (int i=1 ;i<prices.length;i++) { unhold[i] = Math.max(unhold[i-1 ], hold[i-1 ]+prices[i]-fee); hold[i] = Math.max(hold[i-1 ], unhold[i-1 ]-prices[i]); } return unhold[prices.length-1 ]; }
区间 DP
思想：先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。
1 2 3 4 5 6 7 8 9 10 int [][] dp = new int [n][n];for (int i=n-1 ;i>=0 ;i--) { for (int j=i+1 ;j<n;j++) { dp[i][j] = Integer.MIN_VALUE; for (int k=i;k<j;k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1 ][j] + w[i][j]); } } }
1 2 3 Input : "babad"Output: "bab" Note: "aba" is also a valid answer.
方法一：中心扩展法，遍历到数组的某一个元素时，以这个元素为中心，向两边进行扩展，如果两边的元素相同则继续扩展，否则停止扩展。时间复杂度O(n^2),空间复杂度为O(1)
存在问题：但这种方法存在一个问题，当长度为偶数时，例如1221，这是一个回文串，但是并没有中心元素，如果直接用方法1，就会判断其不为回文串。
解决办法：在字符串的中间插入分隔符#，那么1221就会变成1#2#2#1，长度为奇数。而本身长度为奇数的12321，插入分隔符变为1#2#3#2#1，仍然为奇数。那么就可以采用1的方法进行统一判断。插入分隔符后长度为2*n-1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public String longestPalindrome (String s) if (s.length()<2 ) return s; String res = "" ; String new_s = s.charAt(0 ) + "" ; for (int i=1 ;i<s.length();i++) { new_s += "#" + s.charAt(i); } int begin = 0 ; int end = 0 ; for (int i=0 ;i<new_s.length();i++) { int tmp_begin = i-1 ; int tmp_end = i+1 ; while (tmp_begin>=0 && tmp_end<new_s.length()) { if (new_s.charAt(tmp_begin)!=new_s.charAt(tmp_end)) break ; tmp_begin -= 1 ; tmp_end += 1 ; } tmp_begin += 1 ; tmp_end -= 1 ; if (new_s.charAt(tmp_begin)=='#' ) { tmp_begin += 1 ; tmp_end -=1 ; } if ((tmp_end-tmp_begin)>=(end-begin)) { begin = tmp_begin; end = tmp_end; } } res = new_s.substring(begin, end+1 ); res = res.replace("#" ,"" ); return res; }
方法二：动态规划：如果用dp[i][j]保存子串从i 到j是否是回文子串， 如果dp[i][j]为回文，那么dp[i+1][j-1],也一定为回文。
dp[i][j]= s[i]==s[j] && dp[i+1][j-1], 要想求dp[i][j]，要先求出dp[i+1][j-1]求 i 要先求 i+1， 说明 i 要从大到小遍历； 求 j 要先求 j-1， 说明 j 要从小到大遍历； 用dp[i][j]保存子串从i 到j是否是回文子串， 那么 j>=i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public String longestPalindrome (String s) if (s.isEmpty()) { return s; } int n = s.length(); boolean [][] dp = new boolean [n][n]; int left = 0 ; int right = 0 ; for (int i = n - 2 ; i >= 0 ; i--) { dp[i][i] = true ; for (int j = i + 1 ; j < n; j++) { dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<2 ||dp[i+1 ][j-1 ]); if (dp[i][j]&&right-left<j-i){ left=i; right=j; } } } return s.substring(left,right+1 ); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 给你一个正整数数组 arr，考虑所有满足以下条件的二叉树： 1. 每个节点都有 0 个或是 2 个子节点。2. 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。3. 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。 输入：arr = [6 ,2 ,4 ] 输出：32 解释：有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。 24 24 / \ / \ 12 4 6 8 / \ / \ 6 2 2 4
dp[i][j] ：从 i 到 j 的非叶子节点的最小和。dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + max(A[i..k])*max(A[k+1..j]))想求 dp[i][j]， 要先知道 dp[i][k] 和 dp[k+1][j]，k 是从 i 到 j 的一个值。
要求 dp[1][4] ，要先求 dp[1][2] dp[3][4] ， 所以 i 要从大到小遍历，j 从小到大遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public int mctFromLeafValues (int [] arr) int [][] max = new int [arr.length][arr.length]; for (int i=0 ;i<arr.length;i++) { max[i][i] = arr[i]; for (int j=i+1 ;j<arr.length;j++) { max[i][j] = Math.max(arr[j], max[i][j-1 ]); } } int [][] dp = new int [arr.length][arr.length]; for (int i=arr.length-1 ;i>=0 ;i--) { for (int j=i+1 ;j<arr.length;j++) { dp[i][j] = Integer.MAX_VALUE; for (int k=i;k<j;k++) { int tmp = dp[i][k] + dp[k+1 ][j] + max[i][k]*max[k+1 ][j]; dp[i][j] = Math.min(dp[i][j], tmp); } } } return dp[0 ][arr.length-1 ]; }
1 2 3 4 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1 次合并后成为一堆。求出总的代价最小值。 输入：13 7 8 16 21 4 18 输出：239
dp[i][j]：从 i 堆石子到 j 堆石子进行合并最小代价。dp[i][j] = dp[i][k] + dp[k+1][j] + w[i][j], 其中w[i][j]表示 i 到 j 的石子的和。 为了方便我们定义 sum[i] 为从第 0 堆石子到第 i 堆石子的和。那么 w[i][j]=sum[j]-sum[i-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int stoneSum (int [] arr) int [] sum = new int [arr.length+1 ]; for (int i=1 ;i<=arr.length;i++) sum[i] = sum[i-1 ] + arr[i-1 ]; int [][] dp = new int [arr.length][arr.length]; for (int i=arr.length-1 ;i>=0 ;i--) { for (int j=i+1 ;j<arr.length;j++) { dp[i][j] = Integer.MAX_VALUE; for (int k=i;k<j;k++) { int tmp = dp[i][k] + dp[k+1 ][j] + sum[j+1 ]-sum[i]; dp[i][j] = Math.min(dp[i][j], tmp); } } } return dp[0 ][arr.length-1 ]; }
石子合并（环形） 1 有n堆石子排成一圈，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。
注：3题是排成一列，该题是排成一圈。
方法一：将石子复制一遍，由n个堆的环形变成2n个堆的直线形。最终不再是求 dp[0][n-1], 而是在 dp[0][n-1], dp[1][n], dp[2][n+1]...dp[n][2n-1]中取最小值。
相当于我起始位置不一定从 0 开始，可以从任意位置开始，到长度为 n 的地方结束。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public static int stoneSum (int [] stone) int [] arr = new int [stone.length*2 ]; for (int i=0 ;i<stone.length;i++) { arr[i] = stone[i]; arr[i+stone.length] = stone[i]; } int [] sum = new int [arr.length+1 ]; for (int i=1 ;i<=arr.length;i++) sum[i] = sum[i-1 ] + arr[i-1 ]; int [][] dp = new int [arr.length][arr.length]; for (int i=arr.length-1 ;i>=0 ;i--) { for (int j=i+1 ;j<arr.length;j++) { dp[i][j] = Integer.MAX_VALUE; for (int k=i;k<j;k++) { int tmp = dp[i][k] + dp[k+1 ][j] + sum[j+1 ]-sum[i]; dp[i][j] = Math.min(dp[i][j], tmp); } } } int min_val = Integer.MAX_VALUE; int n = stone.length; for (int i=0 ;i<n;i++) min_val = dp[i][n-1 +i]<min_val?dp[i][n-1 +i]:min_val; return min_val; }
方法二： 直接利用环形的动态规划，取余即可。这个暂时不太懂怎么来的。
dp[i][j] = dp[i][k] + dp[(i+k−1)%n+1][j−k] + w[i][j]
1 2 Given the initial sequence ([([]]) ], the longest regularbrackets subsequence is[([]) ]. 找到符合括号匹配的最长子序列的长度。
这道题和回文串的动规方法很像，如果 s[i]==s[j]，那么 dp[i][j] = 2 + dp[i+1][j-1]
但仅仅做上面一个判断是不够的。
比如 s="()()"，dp[0][3] = 2 + dp[1][2] = 2； 显然是不对的。
dp[0][3] = max(dp[0][3], dp[0][0]+dp[1][3], dp[0][1]+dp[2][3], dp[0][2]+dp[3][3])
也就是，我到底是把最外面两个括号当作一个匹配，然后加上里面。还是把最左括号和左面一部分匹配+最右括号和右面一部分匹配。然后看哪种得到的结果最大就是哪种情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static int longestValidParentheses (String s) if (s.length()==0 ) return 0 ; int [][] dp = new int [s.length()][s.length()]; for (int i=s.length()-1 ;i>=0 ;i--) { dp[i][i] = 0 ; for (int j=i+1 ;j<s.length();j++) { if ((s.charAt(i)=='(' && s.charAt(j)==')' )||(s.charAt(i)=='[' && s.charAt(j)==']' )) dp[i][j] = Math.max(dp[i][j], 2 + dp[i+1 ][j-1 ]); for (int k=i;k<j;k++) dp[i][j] = Math.max(dp[i][j], dp[i][k]+dp[k+1 ][j]); } } return dp[0 ][s.length()-1 ]; }
⭐ 整数划分使乘积最大 1 2 3 给出两个整数 n, m, 要求在 n 中加入 m - 1 个乘号，将 n 分成 m 段，求出这 m 段的最大乘积。 输入：111 ，2 输出：11 输入：1111 ，2 输出：121
1 2 3 4 5 6 7 8 我的思考过程： 1. dp[i][j][m]: 从位置i到位置j,分成m段的乘积最大值。2. 那么dp[i][j][m] = dp[i][k][p]*dp[k+1 ][j][m-p-1 ]，但是这样参数太多。3. 我们最终求dp[0 ][len][m] = dp[0 ][k][p]*dp[k+1 ][len][m-p-1 ]4. 可以定义：dp[i][j]:从0 位置到i位置插入了j个乘号得到的最大值。那么原dp[0 ][k][p]可表示为dp[k][p]5. 那么dp[k+1 ][len][m-p-1 ]又没办法表示了。那么我们只能让后一段只有一个数，没有乘号，那么后一段就不需要这么复杂，直接num[k+1. ..len]就行了。6. dp[i][j] = max(dp[i][j], dp[k][j-1 ]*num[k+1. ..len])7. 最终求：dp[len][m-1 ], 所以i和i都要从小到大遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static int maxResult (int n, int m) String s = n + "" ; int [][] dp = new int [s.length()][m]; for (int i=0 ;i<s.length();i++) dp[i][0 ] = Integer.parseInt(s.substring(0 , i+1 )); for (int j=1 ;j<m;j++) { for (int i=j;i<s.length();i++) { for (int k=j-1 ;k<i;k++) { int tmp = dp[k][j-1 ]*Integer.parseInt(s.substring(k+1 , i+1 )); dp[i][j] = Math.max(dp[i][j], tmp); } } } return dp[s.length()-1 ][m-1 ]; }
凸多边形三角划分问题 1 给定一个具有N(N<=50 )个顶点(从1 到N编号)的凸多边形，每个顶点的权值已知。问如何把这个凸多边形划分成N-2 个互不相交的三角形，使得这些三角形顶点的权值的乘积之和最小。
dp[i][j]：表示从顶点 i 到顶点 j 组成的凸多边形划分之后乘积之和的最小值。dp[i][j] = dp[i][k] + dp[k][j] + arr[i]*arr[j]*arr[k]哎😔，，边界太难控制了。。
1 2 3 4 5 6 7 8 9 10 11 12 public int triangleMin (int [] arr) int [][] dp = new int [arr.length][arr.length]; for (int i=arr.length-3 ;i>=0 ;i--) { for (int j=i+2 ;j<arr.length;j++) { dp[i][j] = Integer.MAX_VALUE; for (int k=i+1 ;k<j;k++) dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j] + arr[i]*arr[k]*arr[j]); } } return dp[0 ][arr.length-1 ]; }
1 2 3 4 5 6 7 8 9 10 我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。 示例: n = 10 , 我选择了8. 第一轮: 你猜我选择的数字是5 ，我会告诉你，我的数字更大一些，然后你需要支付5 块。 第二轮: 你猜是7 ，我告诉你，我的数字更大一些，你支付7 块。 第三轮: 你猜是9 ，我告诉你，我的数字更小一些，你支付9 块。 游戏结束。8 就是我选的数字。 你最终要支付 5 + 7 + 9 = 21 块钱。 给定 n ≥ 1 ，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
就是要怎样进行猜数字，才能让自己花费的钱最少。比如n=10，那么一开始猜7，如果大了就猜9，那么需要花费7+9=16块钱赢得游戏。如果一开始猜5，那么大了还要猜7和9，那么就要花费5+7+9=21。所以我们要求最少花费多少钱赢得游戏。
通过上面的解释可以看出这不是二分查找的题，二分查找虽然能保证一定找到你想要的数字，但却不是花费最少的方法。所以是一道动态规划的题。
分析：
1 2 3 4 在1 到n里面，随便猜一个数i，那么此时赢得游戏的最少花费为: truetruetruedp[1. .n] = arr[i] + max(dp[1. .i-1 ], dp[i+1. .n])， 而 dp[1. .i+1 ] 又可以继续分割，随机猜一个数字k, 那么 truetruetruedp[1. .i+1 ] = arr[k] + max(dp[1. .k], dp[k..i+1 ])
麻卖批。。分析到这明显是区间dp啊！！！为什么自己就不能从这么简单的地方开始分析呢。。
定义 dp[i][j]：从位置 i 到位置 j 猜出数字的最小花费。那么我们最终要求的为 dp[1][n] 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int getMoneyAmount (int n) if (n==1 ) return 0 ; int [][] dp = new int [n+1 ][n+1 ]; for (int i=n;i>0 ;i--) { dp[i][i] = 0 ; for (int j=i+1 ;j<=n;j++) { dp[i][j] = Integer.MAX_VALUE; if (j==i+1 ) dp[i][j] = i; for (int k=i+1 ;k<j;k++) dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k-1 ], dp[k+1 ][j])); } } return dp[1 ][n]; }
