dfs-dp-回溯 & speedup

60 Permutation Sequence 字典序第k个排列

Input: n = 3, k = 3
Output: “213”

Bellman-Ford复杂度O（VE）还可以用于检查负圈。全部初始化为0而不是INF。如果第n（N个顶点的循环)还更新了有负圈

Dijkstra：
Bellman 用d[i]+edge（i,j)更新d[j]但是d[i]并不是最短，所以浪费。
思想：找到最短距离已经确定的点d[i]，从它出发更新i的所有邻点。
堆中存储的是每个顶点当前最短距离。

POJ3255

有P条路，有N个点，问从1到N的次短路径是多少。
AC

POJ 3723 征兵

有N女，M男，如果N和M之间有关系，则先招了其中一个，招另一个就可以少付d钱。
最大权森林问题。

POJ 3169 排列牛

输入 N头牛关系好ML的2行，关系不好的MD1行。
关系好的牛1和牛3最大距离不能超过10.
关系差的牛2和牛3最小距离不能小于3.
4 2 1
1 3 10
2 4 20
2 3 3

dp[n]是第n头牛的位置
按编号顺序排列牛所以d[i+1]>=d[i]

49 异位词(相同字符)分组

//todonext
直接拿CharArray的sort重建String当key 49%

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> rst = new ArrayList<>();

    for(String str:strs){
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        List<String> keylist = map.getOrDefault(key, new ArrayList<>());
        if(keylist.size()==0){
            rst.add(keylist);
        }
        keylist.add(str);
        map.put(key,keylist );
    }
    return rst;
}

word search

用全局mark数组58%，改用char修改board98%

展开代码

//    boolean[][] marked;
public boolean exist(char[][] board, String word) {
    int n  = board.length;
    int m = board[0].length;
//        marked = new boolean[n][m];
    for (int i = 0; i <n ; i++) {
        for (int j = 0; j <m ; j++) {
            if(word.charAt(0)!=board[i][j])continue;
            if(dfs(board,0,i,j,word))return true;

        }

    }
    return false;
}

private boolean dfs(char[][] board,int idx,int i,int j,String word){
    if(i>board.length-1||i<0||j>board[0].length-1||j<0||word.charAt(idx)!=board[i][j])return false;

    if(idx==word.length()-1)return true;
    char tmp = board[i][j];
//        marked[i][j] = true;
board[i][j]='0';

    boolean ans = dfs(board,idx+1,i+1,j,word)||
            dfs(board,idx+1,i,j+1,word)||dfs(board,idx+1,i-1,j,word)
            ||dfs(board,idx+1,i,j-1,word);
//        marked[i][j]=false;
    board[i][j]=tmp;
    return ans;
}

Boggle

> board =
> [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
> Given word = "ABCCED", return true.
> Given word = "SEE", return true.
> Given word = "ABCB", return false.
>

494 在数字中间放正负号使之==target

递归的2种写法另一种void用全局变量累加
？？为什么递归中不能写dfs(idx++)
O(2^n)

private int dfs(int[] nums,int S,int pos){
    if(pos == nums.length){
        if(S==0)return 1;
        else return 0;
    }
    int cnt =dfs(nums, S+nums[pos], pos+1)+dfs(nums, S-nums[pos], pos+1);
    return cnt;
}

53%
优化记忆化：用当前的idx和当前的S当key 注意如果用String key=idx+""+S有一个case会报错，应该是数字大的时候混淆了。
sum不会超过1000所以Integer key = idx*10000+S就可以通过。

dp??：
所有可能的target最大值是全部正号sum(a),或者全部负号）dp[2*sum(a)+1]
题目sum最大2k，则dp[4001]

17 九宫格输入法数字对应的字符串

private String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
private void help(List<String> rst,int idx,String digits,String cur){
    if(cur.length()==digits.length()){
        rst.add(cur);
        return;
    }
    if(digits.charAt(idx)>='2'&&digits.charAt(idx)<='9'){
        String num2letter = letters[digits.charAt(idx)-'0'];
        for(int i =0;i<num2letter.length();i++){
            help(rst,idx+1,digits,cur+num2letter.charAt(i));
        }   
    }
}

93 分解Ip地址

dfs

private void dfs(List<String> rst,String s,int idx,String cur,int cnt){
    if(cnt>4)return;
    if(cnt==4&&idx==s.length()){
        rst.add(cur);
    }
    for(int i =1;i<4;i++){
        if(idx+i>s.length())break;
        String tmp = s.substring(idx,idx+i);
        if((tmp.startsWith("0")&&tmp.length()>1)||(i==3&&Integer.parseInt(tmp)>=256))continue;
        dfs(rst,s,idx+i,cur+tmp+(cnt==3?"":"."),cnt+1);
    }
}

784 大小写字母的permutation

'a'-'A'=32所以就是(1<<5)的位置是0或1，但是不会变快
小写和数字都加上这一位继续dfs，大写要

if(idxchar-'A'>=0&&idxchar-'A'<26||idxchar-'a'>=0&&idxchar-'a'<26){
    idxchar = (char)(idxchar^(1<<5));
    dfs(s,idx+1,cur+idxchar);
    idxchar = (char)(idxchar^(1<<5));
}
    dfs(s,idx+1,cur+idxchar);

$C(n,r) = P(n,r)/r!$

46 permutations

全排列：康托编码
https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/permutation-sequence.html

生成全排列的算法: 移动高位
1的全排列只有1，
1，2的全排列考虑2 放在1前，1后
1，2，3的全排列考虑3 放在 1，2 的全排列的左中右3个位置一共3*2 = 6种

给定{1..n-1}的排列，存在n种方法将n插入得到{1..n}的排列
n个球放入r个盒子里
分步递推：$P(n,r)=nP(n-1,r-1)$
分类递推：不选第一个球，方案数$P(n-1,r)$,选第一个球方案数$rP(n-1,r-1)$->$P(n,r)=P(n-1,r)+rP(n-1,r-1)$
O(2^n)复杂度 3ms

if(tmp.size()==nums.length){         
    rst.add(new ArrayList<Integer>(tmp));
    return;
}

一定要复制一份tmp，不然tmp是对象最后tmp会被remove为空

for(int i =0;i<nums.length;i++){
    //dfs的marked
    if(tmp.contains(nums[i]))continue;
    tmp.add(nums[i]);
    help(rst,nums,tmp);
    tmp.remove(tmp.size()-1);
}

O(n!)复杂度只能处理10个数字
不用contains 用markd数组 3ms

展开代码

boolean[] used;
private void dfs(int idx,List<List<Integer>> rst,List<Integer> tmp,int[] nums){
    if(idx>=nums.length){
        rst.add(new ArrayList<>(tmp));
        return;
    }
    //注意 排列无顺序 每次从0开始，但是要去重
    for(int i = 0;i<nums.length;i++){
        if(used[i]) continue;
          used[i] = true;
        tmp.add(nums[i]);
        dfs(idx+1,rst,tmp,nums);
        tmp.remove(tmp.size()-1);
        used[i] = false;   
        }
}
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> rst = new ArrayList<>();
    int n = nums.length;
    used = new boolean[n];
    dfs(0,rst,new ArrayList<>(),nums);
    return rst;
}

方法2 swap java不能int[]->List

SJI算法：可移动数

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int> > ans;
    help(nums,0,ans);
    return ans;
}
void help(vector<int> &num,int begin,vector<vector<int> > &ans){
    if(begin>=num.size()){
        ans.push_back(num);
        return;
    }
    for(int i =begin;i<num.size();i++){
        swap(num[begin],num[i]);
        help(num,begin+1,ans);
        swap(num[begin],num[i]);
    }
}

39 Combination tum target 不重复元素组合求目标

candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

注意这种写法如果输入[1,1,1] 有重复元素的不行
关键：加上start，防止出现3,2,2的重复
组合比排列dfs的时候多一个start,每次只向后取数字
先输出[2,2,3]
44% 15ms

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> rst = new ArrayList<>();
    Arrays.sort(candidates);
    help(rst,candidates,target,new ArrayList<>(),0);
    return rst;
}
private void help(List<List<Integer>> rst,int[] candi,int target,List<Integer> tmp,int idx){
if(target<0)return;
    if (target == 0) {
        rst.add(new ArrayList<>(tmp));
        return;
    }

for (int i = idx ; i <candi.length; i++) {
    //因为排序了，如果之后元素都大则不用向装这个向后找了
    if(candi[i]>target)break;
        tmp.add(candi[i]);
        //可以使用重复元素则idx,不能重复则idx+1
        help(rst,candi, target-candi[i], tmp,i);
        tmp.remove(tmp.size()-1);
    }
}

如果要先输出长度短的：先输出[7] 加个长度d和总长度len
可以作为从N个数里选len个数的模板

public List<List<Integer>> combinationSumLenOrder(int[] candidates, int target) {
    List<List<Integer>> rst = new ArrayList<>();
    Arrays.sort(candidates);
    //最长用第一个元素target/candi[0]次
    for (int i = 1; i <=target/candidates[0] ; i++) {
        dfs(rst,candidates,new ArrayList<>(),target,0,0,i);
    }
    return rst;
}
private void dfs(List<List<Integer>> rst,int[] candi,List<Integer> tmp,int target,int d,int idx,int len){

    if(d==len){
        if(target==0)rst.add(new ArrayList<>(tmp));
        return;
    }
    for (int i = idx; i <candi.length ; i++) {
        if(candi[i]>target)break;
        tmp.add(candi[i]);
        dfs(rst,candi,tmp,target-candi[i],d+1,i,len);
        tmp.remove(tmp.size()-1);
    }
}

lt135 有重复元素的可以利用一个元素多次的comb sum

输入[1,1,1],target = 2 -> [[1,1]]

方法1.用set去重

Set<Integer> set = new HashSet<>();
    for(int i:candidates)set.add(i);
    int[] nums = new int[set.size()];
    int idx =0;
    for(int i:set){
        nums[idx++] = i;
    }

方法2.加一行

for(int i = idx;i<candidates.length;i++){
    if(candidates[i]>target)break;
    //跳过重复的
    if(i>0&&candidates[i]==candidates[i-1])continue;
    tmp.add(candidates[i]);
    dfs(rst,candidates,target-candidates[i],tmp,i);
    tmp.remove(tmp.size()-1);
}

40 有重复元素且每个元素只能用一次的combsum

1.直接用Set<List>->List<List> 34ms 11%

加上注意一定是>idx,不然[1,1]会被跳过
if(i>idx&&candi[i]==candi[i-1])continue;
并且dfs(rst,candi, target-candi[i], tmp,i+1);

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> rst = new ArrayList<>();
    Arrays.sort(candidates);
    dfs(rst,candidates,target,new ArrayList<>(),0);
    return new ArrayList<>(rst);
}
private void dfs(List<List<Integer>> rst,int[] candi,int target,List<Integer> tmp,int idx){
    if(target<0)return;
    if (target == 0) {
        rst.add(new ArrayList<>(tmp));
        return;
    }
    for (int i = idx ; i <candi.length; i++) {
        if(candi[i]>target)break;
        //不是第一个元素，如果是[1,1,1] 这一层不找相同的元素
       if(i>idx&&candi[i]==candi[i-1])continue;
        tmp.add(candi[i]);
        //可以使用重复元素则idx,不能重复则idx+1
        dfs(rst,candi, target-candi[i], tmp,i+1);
        tmp.remove(tmp.size()-1);
    }
}

216 从1-9中选k个数字组成target

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

AC 78% 1ms

lt564 无重复，可用多次，顺序不一样也计数，组成target的个数 dp

给出 nums = [1, 2, 4], target = 4
可能的所有组合有：
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
返回 6

45jump game cnt 2do next time

dp:

 private int jumpdp(int[] nums){
    int n = nums.length;
    int[] dp =  new int[n];
    if(n == 0||nums[0] ==0)return 0;
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        dp[i] = Integer.MAX_VALUE;
        for (int j = 0; j <i ; j++) {
            if(i<=j+nums[j]&&dp[j]!= Integer.MAX_VALUE){
                dp[i] = Math.min(dp[i],dp[j]+1);
                break;
            }
        }
    }
    return dp[n-1];
}

BFS：

public int jumpBFS(int[] nums){
    if(nums==null||nums.length<2)return 0;
    int level = 0;
    int cur = 0;
    int max =0;
    int i =0;
    //cur-i+1=1,level++; i<=cur,i++,max = 2;cur = 2;
    //cur=2,i=1;level++; i<=2,i++,max = 4,max>=n-1 return 2;
    while (cur-i+1>0){
        level++;
        for(;i<=cur;i++){
            max = Math.max(max,nums[i]+i);
            if(max>=nums.length-1)return level;
        }
        cur = max;
    }

    return 0;
}

递归

public int minJumpRecur(int[] arr){
    int n = arr.length;
    memo = new int[n][n];
    return jump(arr, 0, n-1);
}
int[][] memo;
private int jump(int[] steps,int from,int end){
//        System.out.println(from+" "+end);
    if(from==end)return 0;
    //不可达
    if(memo[from][end]!=0)return memo[from][end];
    if(steps[from]==0)return Integer.MAX_VALUE;
    int min = Integer.MAX_VALUE;
    //当前可以到达的范围是[from,from+step[from]]
    for(int i = from+1;i<=end&&i<=from+steps[from];i++){
        int jumps = jump(steps,i , end);
        if(jumps!=Integer.MAX_VALUE&&jumps+1<min){
            min = jumps+1;
            memo[from][end] = min;
        }
    }
    return min;
}

最正常的做法：

public int jump(int[] nums) {
    if(nums==null||nums.length<2)return 0;
    int res = 0;
    int curMax = 0;
    int maxNext = 0;
    //i=0,max = 2 i==cur ->res++,cur = max=2
    //i=1,max = max(2,4)=4, i!=cur
    //i=2,max = max(4,3)=4, i==cur res++,cur = max=4
    //i=3,max = max(4,4)=4, i!=cur break
    //不需要走到i=4,max = max(4,4+4)=8,i==cur res++,cur=max
    for (int i = 0; i < nums.length-1; i++) {
        maxNext = Math.max(maxNext,i+nums[i] );
        if(i==curMax){
          res++;
          curMax = maxNext;
        }
    }
    return res;
}

743 从一个node广播，让所有节点收到最多要多久单源最短路径

time[[2,1,1],[2,3,1],[3,4,1]] times[i] = (u, v, w) u到v花费w
N个节点，从K发送
dijkstra如果用heap可以从$N^2$->$NlogN+E$ O(N+E)
Bellman-Ford O(NE)稠密图不好空间O(N) 可以有负的路径
Floyd-Warshall O(N^3)

heapDijkstra
78%
//todo faster

dijkstra:每次扩展距离最近的点 70% 32ms

public int networkDelayTimeDFSDj(int[][] times, int N, int K) {
    Map<Integer,List<int[]>> graph = new HashMap<>();
    for(int[] edge:times) {
        if (!graph.containsKey(edge[0]))
            graph.put(edge[0], new ArrayList<int[]>());
        graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    int[] dis = new int[N];
    Arrays.fill(dis, Integer.MAX_VALUE);
    dis[K-1]=0;
    boolean[] marked = new boolean[N+1];
    while (true){
        int candNode =-1;
        int canDist = Integer.MAX_VALUE;
        for (int i = 1; i <= N ; i++) {
            //最近的点
            if(!marked[i]&&dis[i-1]<canDist){
                canDist = dis[i-1];
                candNode = i;
            }
        }
//            System.out.println(candNode);
        //都当作扩展点过了,
        if(candNode<0)break;
        marked[candNode] = true;
        //最近点的邻接
        if(graph.containsKey(candNode))
            for(int[] next:graph.get(candNode))
                dis[next[0]-1] = Math.min(dis[next[0]-1],dis[candNode-1]+next[1]);
//            System.out.println(Arrays.toString(dis));
    }
    int ans = 0;
    for(int cost:dis){
        if(cost==Integer.MAX_VALUE)return -1;
        ans= Math.max(ans,cost);
    }
    return ans;
}

dfs: 邻接表建图，递归终止条件:到达所有点花费的时间已经是最小的了
dfs Hashmap6% 改成数组11% 124ms

public int networkDelayTimeDFS(int[][] times, int N, int K) {
    //creategraph
    Map<Integer,List<int[]>> graph = new HashMap<>();
    for(int[] edge:times) {
        if (!graph.containsKey(edge[0]))
            graph.put(edge[0], new ArrayList<int[]>());
        graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }//end-creategraph
    //只是为了加速， 不排序2.8% 352ms
    for(int node:graph.keySet()){
        Collections.sort(graph.get(node),(a,b)->a[1]-b[1]);
    }
    dis = new int[N];
    Arrays.fill(dis, Integer.MAX_VALUE);
    dfs(graph,K,0);
    int ans = 0;
    for(int cost:dis){
        ans = Math.max(ans,cost);
    }
    return ans==Integer.MAX_VALUE?-1:ans;
}
//用于记录到某点的距离，如果到这个点花费的时间已经超过记录的最小值了，不对这个点dfs了。
int[] dis;
private void dfs(Map<Integer,List<int[]>> graph,int node,int elased){
    if(elased>=dis[node-1])return;
    dis[node-1]=elased;
    if(graph.containsKey(node)){
        for(int[] nei:graph.get(node))
            dfs(graph,nei[0],elased+nei[1]);
    }
}

/**Bellman Ford 边集
 * 从K点广播给N个点需要的最少时间
 * @param times u到v花费w秒 1 <= w <= 100.
 * @param N N will be in the range [1, 100].
 * @param K
 * @return
 */
public int networkDelayTime(int[][] times, int N, int K) {
    int max_time = 100*101;
    int[] dis = new int[N];
    int rst = Integer.MIN_VALUE;
    Arrays.fill(dis,max_time);
    //起点
    dis[K-1] = 0;
    //其他N-1个点
    for (int i = 1; i <N ; i++) {
        //遍历n次边的数组
        for(int[] edge:times){
            int u = edge[0]-1;
            int v = edge[1]-1;
            int w = edge[2];
            //动态规划
            dis[v] = Math.min(dis[v],dis[u]+w);
        }

    }
    for(int cost:dis){
        rst = Math.max(cost,rst );
    }
    return rst == max_time?-1:rst;
}

弗洛伊德算法边集

public int networkDelayTimeF(int[][] times, int N, int K) {
    int max_time = 100*101;
    //二维数组 表示i到j的最短路径
    int[][] dis = new int[N][N];
    for(int[] d:dis){
        Arrays.fill(d,max_time);
    }
    for(int[] time:times){
        dis[time[0]-1][time[1]-1] = time[2];
    }
    for (int i = 0; i <N ; i++) {
        dis[i][i] =0;
    }
    for (int k = 0; k <N ; k++) 
        for (int i = 0; i <N ; i++) 
            for (int j = 0; j <N ; j++) 
                //三维动态规划
                dis[i][j] = Math.min(dis[i][j],dis[i][k]+dis[k][j]);
    int ans = Integer.MIN_VALUE;
    for (int i = 0; i <N ; i++) {
        if(dis[K-1][i]>=max_time)return -1;
        ans = Math.max(ans,dis[K-1][i]);
    }
    return ans;
}

343 整数拆分并使乘机最大

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

int[] memo;
public int IntegerBread(int n){
    memo = new int[n+1];
    return ib(n);
}
private int ib(int n){
    if(memo[n]!=0)return memo[n];
    if(n==1)return 1;
    int res = -1;
    for(int i=1;i<n;i++){
        res = Math.max(res,Math.max(i*(n-i),i*ib(n-i)));
        memo[n]=res;
    }
    return res;
}

dp：

public  int integerBreak(int n) {
   int[] dp = new int[n+1];
    dp[1]=1;
    
    for(int i =2;i<=n;i++){
        for(int j=1;j<=i-1;j++){
            dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
        }
    }
    return dp[n];

数学方法：
考虑f=x(N-x) 当x=N/2的时候取最大值。
所以当N是偶数时，最大值是(N/2)(N/2)
当N是奇数，最大值是(N-1)/2 (N+1)/2
6, 3 * 3>2 * 2 * 2

public int integerBreak(int n) {
    if(n==2) return 1;
    if(n==3) return 2;
    int product = 1;
    while(n>4){
        product*=3;
        n-=3;
    }
    product*=n;
    
    return product;
}

787 中间最多停留k次的，最小花费路线

Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
from src to dst with up to k stops 最小花费
Output: 200

dfs：复杂度n^(k+1)
1.cost边集->邻接表

Map<Integer, Map<Integer, Integer>> edgeC2graph(int[][]edges,int n){
    Map<Integer, Map<Integer, Integer>> graph = new HashMap<>(n);
    for (int[] edge : edges) {
        graph.putIfAbsent(edge[0], new HashMap<>());
        graph.get(edge[0]).put(edge[1], edge[2]);
    }
    return graph;
}

dfs 常规回溯

Map<Integer, Map<Integer, Integer>> graph;
boolean[] visited;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    graph = new HashMap<>(n);
    for (int[] edge : flights) {
        graph.putIfAbsent(edge[0], new HashMap<>());
        graph.get(edge[0]).put(edge[1], edge[2]);
    }
    visited = new boolean[n];
    visited[src] = true;
    dfs(graph, src, dst, K + 1, 0);


    return ans == Integer.MAX_VALUE ? -1 : ans;
}

int ans = Integer.MAX_VALUE;
private void dfs(Map<Integer, Map<Integer, Integer>> graph, int src, int dst, int k, int cost) {
    if (src == dst) {
        ans = cost;
        return;
    }
    if (k == 0) return;
    Map<Integer, Integer> adj = graph.getOrDefault(src,new HashMap<>());
    for (int key : adj.keySet()) {
        if (visited[key]) continue;
        if (cost + adj.get(key) > ans) continue;
        visited[key] = true;
        dfs(graph, key, dst, k - 1, cost + adj.get(key));
        visited[key] = false;
    }
}

94ms
bfs:复杂度n^(k+1) Dijkstra 最小优先队列扩展，先扩展加上下一个点cost最小的

public int findCheapestPriceDj(int n, int[][] flights, int src, int dst, int k) {
    Map<Integer, Map<Integer, Integer>> graph = edgeC2graph(flights, n);
    //每次选cost最小的先扩展
    Queue<int[]> que = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    que.add(new int[]{0,src,k+1});
    while(!que.isEmpty()){
        int[] top = que.remove();
        int price = top[0];
        int city = top[1];
        int stops = top[2];
        if(city == dst)return price;
        if(stops>0){
            Map<Integer, Integer> adj = graph.getOrDefault(city, new HashMap<>());
            for(int a:adj.keySet()){
                que.add(new int[]{price+adj.get(a),a,stops-1});
            }
        }
    }
    return -1;
}

bellman-ford 单源到所有点的最短路径kn^2 dp
dp[k][v] 从起点到v最多k次stop的最小花费

public int findCheapestPriceDp(int n, int[][] flights, int src, int dst, int k) {
    int max = 10001*(k+2);
    //走1~k+1步
    int[][] dp = new int[k+2][n];
    for(int[] ints:dp){
        for (int j = 0; j < n; j++) {
            ints[j] = max;
        }
    }
    dp[0][src] = 0;
    //如果不限制中间k个点，则可以遍历n次
    for (int i = 1; i <= k+1; i++) {
        //走i步走到src ， cost 0
        dp[i][src] = 0;
        for(int[] flight:flights){
            //关键
            dp[i][flight[1]] = Math.min(dp[i][flight[1]],dp[i-1][flight[0]]+flight[2]);
        }
    }
    return dp[k+1][dst]>=max?-1:dp[k+1][dst];
}

？96 不同的BST数量 catalan数

Input: 3
Output: 5

(为什么是乘)

1个节点只有1种，2个节点1    2 一共两种
                      \  /
                      2  1
3个节点1      2      3
      / \    / \    / \
   （0）(2) (1)(1) (2)(0)
      1x2  + 1x1  + 2x1

当n=5 $T[4]+T[1][3]+T[2][2]+T[3][1]+T[4]$

左子树有j个节点，右子树有n-j-1个节点

int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
//节点个数
for(int i =2;i<=n;i++){
    //左边j个
    for(int j =0;j<i;j++){
        //注意是累加
        dp[i]+=dp[j]*dp[i-j-1];
    }
}
return dp[n];

dfs:

public int numTreesDfs(int n) {
    int[] memory = new int[n+1];
    return dfs(n,memory);
}
public int dfs(int n,int[] memroy){
    if(n==0||n==1)return 1;
    if(memroy[n-1]!=0)return memroy[n-1];
    int sum = 0;
    for (int i = 1; i <=n ; i++) {
        sum+=dfs(i-1,memroy)*dfs(n-i,memroy);
    }
    memroy[n-1] = sum;
    return sum;
}

1 2	int ans[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190}; return ans[n];

int res = 0;
if(n<=1)return 1;
for (int i = 0; i < n; i++) {
    res += catalan(i) * catalan(n - i - 1);
}

二项式系数

private int C(int a,int b){
    long res = 1;
    for(int i =0;i<Math.min(b,a-b);i++){
        res=res*(a-i)/(i+1);
    }
    return (int)res;
}
//C(2n,n)/(n+1)
public int catalen2(int n){
    int c =C(2*n,n);
    return c/(n+1);
}

847 BFS边可以重复访问的访问所有点的最短路径

graph.length = N

Input: [[1,2,3],[0],[0],[0]] 邻接表
Output: 4
Explanation: One possible path is [1,0,2,0,3]

dp：比tsp少判断一次next已经是访问过的点

public int shortestPathLengthDP(int[][] graph) {
    int n = graph.length;
    int[][] dp = new int[n][1<<n];
    Deque<State> que = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i],Integer.MAX_VALUE);
        dp[i][1<<i]=0;
        que.add(new State(i,1<<i));
    }
    while(!que.isEmpty()){
        State state = que.poll();
        for(int next:graph[state.source]){
            int nextMask = state.mask|(1<<next);
            if(dp[next][nextMask]>dp[state.source][state.mask]+1){
                dp[next][nextMask] = dp[state.source][state.mask]+1;
                que.add(new State(next,nextMask));
            }
        }
    }
    int res = Integer.MAX_VALUE;
    for (int i = 0; i <n ; i++) {
        res = Math.min(res, dp[i][(1<<n)-1]);
    }
    return res;
}

BFS：

定点可以访问多次，用当前搜索节点和当前访问过的节点mask作为visited数组
bfs第一层每个顶点都可以作为出发点
que中存储pair<当前节点，访问过的节点>

展开代码

class Pair<K,V>{
        K key;
        V value;
}
public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    int endState = (1<<n)-1;
    Deque<Pair<Integer,Integer>> que = new ArrayDeque<>();
    boolean [][] visited = new boolean[n][1<<n];
    for(int i=0;i<n;i++){
        que.add(new Pair<>(i,1<<i));
    }
    int step =0;
    while(!que.isEmpty()){
        int size = que.size();
        while(size-->0){
            Pair<Integer, Integer> front = que.poll();
            Integer cur = front.key;
            Integer state = front.value;
            // mask全是1，访问了所有点
            if(state == endState) return step;
            if(visited[cur][state])continue;
            visited[cur][state] = true;
            for(int next:graph[cur]){
                que.add(new Pair<>(next,state|(1<<next)));
            }
        }
        step++;
    }
    return -1;
}

60 Permutation Sequence 字典序第k个排列

POJ3255

POJ 3723 征兵

POJ 3169 排列牛

49 异位词(相同字符)分组

word search

Boggle

494 在数字中间放正负号使之==target

17 九宫格输入法数字对应的字符串

93 分解Ip地址

784 大小写字母的permutation

46 permutations

39 Combination tum target 不重复元素组合求目标

lt135 有重复元素的可以利用一个元素多次的comb sum

40 有重复元素且每个元素只能用一次的combsum

216 从1-9中选k个数字组成target

lt564 无重复，可用多次，顺序不一样也计数，组成target的个数 dp

45jump game cnt 2do next time

743 从一个node广播，让所有节点收到最多要多久 单源最短路径

343 整数拆分 并使乘机最大

787 中间最多停留k次的，最小花费路线

？96 不同的BST数量 catalan数

847 BFS边可以重复访问的访问所有点的最短路径

743 从一个node广播，让所有节点收到最多要多久单源最短路径

343 整数拆分并使乘机最大