DP

#Medium  62. Unique Paths

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

思路：如果单列或者单行的，那只能是一直笔直走，一条路（base case)

否则opt[i][j] = opt[i-1][j] + opt[i][j-1]; 就是上边走来或者左边走来的相加

填表按照行即可，然后最终角落位置即是我们要求的值

错误：数组0 -> n-1没注意好而不是1 -> n，要注意

#Medium  64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

思路：如同上题，只不过是求左边来和上边来的min再加上本身即可

这里可以考虑更加节省空间方法，每一行只需要上一行所以我们可以始终保持两行，用两个一位数组即可，而不用矩阵

错误：算上一行时第一个格子相对是变化的，不是填死的1哦

0-1 Knapsack

Given a knapsack which can hold w pounds of items, and a set of items with weight w1, w2, ... wn. Each item has its values1,s2,...,sn. Try to select the items that could put in knapsack and contains most value.

思路：0-1背包问题，首先想到表应该如何建立呢，选不选择物品剩余可用重量会变，选择到了那个物品也会变，所以这两项就是我们的表

每走到一个物品，我们都看一下，能否摆得下，摆不下就是用它前一个物品的值填入，摆得下那要看摆入这个物品是否合适，因为摆下这个势必挤掉了别人的位子，到底哪个更好需要比较。

注意：这里的0行0列是我们多出来的，所以什么变量时是length+1和capacity+1，但是由于java默认值是0所以0行0列可以不需要去赋值，直接从1开始计算即可

#Medium 322. Coin Change

（比较难，我没想出来——

ou are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

coins = [1, 2, 5], amount = 11

return 3 (11 = 5 + 5 + 1)

Example 2:

coins = [2], amount = 3

return -1.

思路：与0-1背包的不同之处就是硬币可以一直反复用，base case就是只用第一枚硬币，那只有被他能整除的数字才能是返回整数其他都返回-1； 然后对所用到硬币和当前还需要的价值来填表。该面值已经大于所需，那就返回上一行结果。否则，就遍历可以用到的个数，找出最小值，或者会一个都找不到。

错误：注意，价格那一列变化~

#Medium 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.Given [10, 9, 2, 5, 3, 7, 101, 18],The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

思路：我们首先维持一个max变量，还有一个一维的表格，每往前走一格，我都遍历一遍前面所走过的，当然只有比我小的在我考虑范围内。每算完一格，就更新max，最终返回max。

错误：不是返回一维表格中的最后一个格子，而是返回我们所一直记录的max，才是当前整个数组最长的递增序列。

Matrix Multiplication

如果是两个矩阵相乘A*B，那么不存在优化可能，只有一种结果

如果是两个以上就会存在选择，从中间哪里分开

例如：(A1....Ak)(Ak+1.... An)

T(1,n)=T(1,k)+T(k+1,n)+po*pk+1*pn+1

如何填这个二维表格，是对角线都是0，因为一个矩阵和自己的相乘是无计算次数的，然后斜着往上填，直到最右上角。

最终返回T(0,n-1)即可

这里注意是po*pk+1*pn+1而不是po*pk*pn!搞错了

错误：下标一直搞错

#Hard 87. Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

思路：先考虑递归，首先他们长度一样里面含的字母全一样，才可能是变换后一样的。S1分为A1,B1两部分。S2分为A2, B2两部分。那如果S1和S2是Scramble的话，那么A1和A2并且B1和B2是Scramble， 或者A1和B2并且A2和B1是Scramble。

这里如何检验两个string里面包换的字母都一样呢？

char[] c1 = s1.toCharArray();

char[] c2 = s2.toCharArray();

Arrays.sort(c1);

Arrays.sort(c2);

if (!Arrays.equals(c1, c2)) { return false; }

注意这里用的都是Arrays的方法; If you don't specify endIndex, java substring() method will return all the characters from startIndex.

String s1="javatpoint";  

System.out.println(s1.substring(2,4));//returns va  

System.out.println(s1.substring(2));//returns vatpoint  

#Medium 474. Ones and Zeroes

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Input:Array = {"10", "0", "1"}, m = 1, n = 1Output:2Explanation:You could form "10", but then you'd have nothing left. Better form "0" and "1".

思路：用递归也是可以完成的，但是这里的选不选和所剩余的0，1个数，其实类似于0-1背包中的物品和剩余重量。可以归为0-1背包问题，想到这个方法，这题目就可以轻松完成。

注意：0-1背包是两维填表，这个就是三维了