[数据结构与算法]动态规划学习

动态规划的代码学习

import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;

public class DynamicProgramming {

    //打印字符串的子串
    public static List<String>substring(String s)
    {
        char[] str=s.toCharArray();
        List<String>ans=new ArrayList<>();
        int i,j;
        String tmp="";
        char[] tmp2;
        for(i=0;i<str.length;i++)
        {
            tmp=String.valueOf(str[i]);
            ans.add(tmp);
            for(j=i+1;j<str.length;j++)
            {
                tmp=tmp+String.valueOf(str[j]);
                ans.add(tmp);
            }
        }
        return ans;
    }



    //打印字符串的所有子序列（子序列比子串更自由）
//    public static List<String> subsequence(String s)
//    {
//         char[] str=s.toCharArray();
//         String path="";
//         List<String>ans=new ArrayList<>();
//         process1(str,0,ans,path);
//         return ans;
//    }
//
//public static void process1(char[]str,int index,List<String>ans,String path)
//{
//if(index==str.length)
//{
//    ans.add(path);
//    return;
//}
//String no=path;
//process1(str,index+1,ans,no);
//String yes=path+String.valueOf(str[index]);
//process1(str,index+1,ans,yes);
//}

public static List<String>subsequence(String s)
    {

        char[] str=s.toCharArray();
        String tmp="";
        int i,j;
        List<String>ans=new ArrayList<>();
        if(s==null||s.length()<=0)
        {
            return ans;
        }
        process1(str,0,ans,tmp);

         return ans;

    }

    public static void process1(char[] str,int index,List<String>ans,String tmp)
    {
        if(index==str.length)
        {

            ans.add(tmp);
            return;//这里要有返回
        }
        //要这个字符或者不要这个字符
        String yes="";
        yes=tmp+String.valueOf(str[index]);
        process1(str,index+1,ans,yes);
        String no=tmp;
        process1(str,index+1,ans,tmp);

    }


    public static List<String>subsequence_norepeat(String s)
    {

        char[] str=s.toCharArray();
        String tmp="";
        int i,j;
        HashSet<String>set=new HashSet<>();

        process_norepeat(str,0,set,tmp);
        List<String>ans=new ArrayList<>();
for(String cur:set)
{
    ans.add(cur);
}
        return ans;

    }

    public static void process_norepeat(char[] str,int index,HashSet<String>set,String tmp)
    {
        if(index==str.length)
        {

            set.add(tmp);
            return;//这里要有返回
        }
        //要这个字符或者不要这个字符
        String yes="";
        yes=tmp+String.valueOf(str[index]);
        process_norepeat(str,index+1,set,yes);
        String no=tmp;
        process_norepeat(str,index+1,set,tmp);

    }




    //打印字符串全排列
    public static ArrayList<String>permutation(String str)
    {
      ArrayList<String>res=new ArrayList<>();
      if(str==null||str.length()==0)
      {
          return res;
      }
      char[] chs=str.toCharArray();
      process_permutation(chs,0,res);

      return res;
    }
//str[0..i-1]已经做好决定的
    //str[i...]都有机会来到i位置
    //i终止位置，str当前的样子，就是一种结果，放入arraylist

    public static void process_permutation(char[] chs,int index,ArrayList<String>res)
    {
        if(index==chs.length)
        {
            res.add(String.valueOf(chs));
            return;

        }
        int i,j;
        for(i=index;i<chs.length;i++)
        {
            swap(chs,i,index);
            process_permutation(chs,index+1,res);
            swap(chs,i,index);
        }

    }
    public static void swap(char[] chs,int i,int j)
    {
        char tmp;
        tmp=chs[i];
        chs[i]=chs[j] ;
        chs[j]=tmp;
    }

    //从左往右的尝试模型1
    //1对应A  2对应B  3对应C
    //111转换为“AAA”,"KA","AK"
    public static int number(String str)
    {
      if(str==null||str.length()==0)
      {
          return 0;
      }
      char[] chs=str.toCharArray();
      int res=0;
      res=process(chs,0);
      return res;
    }
    public static int process(char[] chs,int index)
    {
        int i,j,res=0;
        if(index==chs.length)
        {
          return 1;
        }
        if(chs[index]=='0')
        {
            return 0;
        }
        if(chs[index]=='1')
        {
            res=process(chs,index+1);
            if(index+1<chs.length)
            {
                res+=process(chs,index+2);
            }
        }
        if(chs[index]=='2')
        {
            res=process(chs,index+1);
            if(index+1<chs.length&&(chs[index]>='0'&&chs[index]<='6'))
            {
                res+=process(chs,index+2);
            }
        }
        return res;


    }

    //从左往右的尝试模型2背包问题
    public static int getMaxValue(int[] w,int[] v,int bag)
    {
        int res;
        res=process(w,v,0,0,bag);
        return res;
    }
    //不变：w[] v[] bag
    //index...最大价值
    //0....index-1上做了货物的选择，使得你已  经达到的重量是多少alreadyW
    //如果返回-1，认为没有方案
    //如果不返回-1，认为返回的值是真实价值
    //
    public static int process(int[] w,int[] v,int index,int alreadyW,int bag)
    {
        int res=0;
        if(alreadyW>bag)
        {
            return -1;
        }
        //重量没超
        if(index==w.length)
        {
            return 0;
        }
        //如果没要这个当前货物
        int p1=process(w,v,index+1,alreadyW,bag);
        //如果要了当前货物
        int p2next=process(w,v,index+1,alreadyW+w[index],bag);
        int p2=-1;
        if(p2next!=-1)
        {
            p2=v[index]+p2next;
        }
        res=Math.max(p1,p2);
        return res;
    }




    //N皇后

    public static int NQueen(int n)
    {
        if(n<=2)
        {
            return 0;
        }
        int[] record=new int[n];
        int res=process1(0,record,n);
        return res;

    }
    //index表示第几行
    public static int process1(int index,int[] record,int n)
    {
        int res=0;
        if(index==n)
        {
            return 1;
        }
        //j表示第几列
        for(int j=0;j<n;j++)
        {
            if(isValid(record,index,j))
            {
                record[index]=j;
                res+=process1(index+1,record,n);
            }
        }



        return res;
    }

    public static boolean isValid(int[] record,int i,int j)
    {
        int k;
        for(k=0;k<i;k++)
        {
            if(j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k))
            {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args)
    {
         System.out.print("该字符的所有子序列：");
         String a1="abcbcq";
         List<String>ans1=subsequence(a1);
         System.out.print(ans1);
         System.out.println("");

        System.out.print("该字符的所有子序列（不包含重复子序列）：");
        List<String>ans3=subsequence_norepeat(a1);
        System.out.print(ans3);
        System.out.println("");


        System.out.print("该字符的所有子串：");
         List<String>ans2=substring(a1);
         System.out.print(ans2);
        System.out.println("");

        System.out.print("该字符的全排列：");
        ArrayList<String>ans4= permutation(a1);
        System.out.print(ans4);
        System.out.println("");

        System.out.print("转换的总数：");
        String a7="11111";
        int ans5= number(a7);
        System.out.print(ans5);
        System.out.println("");

        System.out.print("所能获得的最大价值为：");
       int[] w={2,3,1,9};
       int[] v={2,3,1,9};
       int bag=10;
        int ans6=getMaxValue(w,v,bag);
        System.out.print(ans6);
        System.out.println("");




        System.out.print("N皇后：");
        int num=6;
        int ans7=NQueen(num);
        System.out.print(ans7);
        System.out.println("");

    }
}