|
阅读该文章预计90分钟
动态规划
一：初步认识动态规划
1.1：介绍递归和动态规划
暴力递归：
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件（base case）
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
动态规划：
- 从暴力递归来
- 将每一个子问题的解记录下来，避免重复计算
- 把暴力递归的过程，抽象成立状态表达
- 并且存在化简状态表达，使其更加简洁的可能
二：求阶乘
2.1：思路讲解
暴力递归
n！只为了求n*（n-1）
我们也可以for循环，相乘每一个数
看code
2.2：Java代码
package xyz.fudongyang.basic.class_08.my;
public class Code_01_Factorial {
public static long getFactorial1(int n) {
if(n == 1){
return 1;
}
return n * getFactorial1(n-1);
}
public static long getFactorial2(int n) {
long result = 1L;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
int n = 5;
System.out.println(getFactorial1(n));
System.out.println(getFactorial2(n));
}
}
三：汉诺塔问题
3.1：题目介绍
链接：原题
来源：牛客网
我们有由底至上为从大到小放置的 n个圆盘，和三个柱子（分别为左/中/右），开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，要求一次只能移动一个圆盘，而且大的圆盘不可以放到小的上面。
请实现一个函数打印最优移动轨迹。
给定一个 int n ，表示有n个圆盘。请返回一个 string 数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。
3.2：思路讲解
只能小压大 不能大压小
三个杆：form to help
from：原始数据
to：目标杆
help：辅助杆
暴力递归步骤：
1：我把1~n-1从from移到help，from只剩n
2：我把from的n移动的to上
3：我把1~n-1从help移动到to
看code
3.3：Java代码
package xyz.fudongyang.basic.class_08.my;
public class Code_02_Hanoi {
public static void hanoi(int n) {
if (n > 0) {
func(n, "left", "mid", "right");
}
}
public static void func(int n, String from, String help, String to) {
if (n == 1) {
System.out.println("Num: " + n + " from " + from + " to " + to);
}else {
func(n-1,from,to,help);
System.out.println("Num: " + n + " from " + from + " to " + to);
func(n-1,help,from,to);
}
}
public static void main(String[] args) {
int n = 3;
hanoi(n);
}
}
四：打印一个字符串的所有子序列，包括空串
4.1：思路解析
什么叫所有子序列？
比如“abc”字符串，他的所有子序列是【“abc”、“ab”、“ac”、“bc”、“a”、“b”、“c”、“”】
如何做出动态规划的决策？
字符串组成序列数组
字符串：“a b c”
下标： 0 1 2
递归暴力求解：
我们可以在0位置上选择，要这个0位置的还是不要，两种情况
我们可以在1位置上选择，要这个1位置的还是不要，两种情况
我们可以在1位置上选择，要这个1位置的还是不要，两种情况
穷举所有答案，暴力递归，一会看code
动态规划求解：
4.2：Java代码（递归）
package xyz.fudongyang.basic.class_08;
import java.util.ArrayList;
import java.util.List;
public class Code_03_Print_All_Subsquences {
public static void printAllSubsquence(String str) {
char[] chs = str.toCharArray();
process(chs, 0,"");
}
public static void process(char[] chs,int i,String res){
if (i == chs.length){
System.out.println(res);
return;
}
process(chs,i+1,res);
process(chs,i+1,res+chs[i]);
}
public static void main(String[] args) {
String test = "abc";
printAllSubsquence(test);
}
}
五：打印一个字符串的全排列
5.1：思路解析
打印一个字符串的全排列
例如：”acc“
则他的全排列就是”acc“、”cac“、”cca“
如何去做？
我们让数组的第一个位置让大家轮流做
然后第二个位置让剩余的人轮流做
依次类推
看code
5.2：Java代码
package xyz.fudongyang.basic.class_08.my;
import java.util.HashSet;
public class Code_04_Print_All_Permutations {
public static void printAllPermutations1(String str) {
char[] chars = str.toCharArray();
process(chars, 0);
}
private static void process(char[] chars, int i) {
if (i == chars.length) {
System.out.println(chars);
return;
}
for (int j = i; j < chars.length; j++) {
swap(chars, i, j);
process(chars, i + 1);
swap(chars, i, j);
}
}
public static void printAllPermutations2(String str) {
char[] chars = str.toCharArray();
process2(chars, 0);
}
private static void process2(char[] chars, int i) {
if (i == chars.length) {
System.out.println(chars);
return;
}
HashSet<Character> existChar = new HashSet<>();
for (int j = i; j < chars.length; j++) {
if (!existChar.contains(chars[j])) {
swap(chars, i, j);
process2(chars, i + 1);
swap(chars, i, j);
existChar.add(chars[j]);
}
}
}
private static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
public static void main(String[] args) {
String test1 = "abc";
printAllPermutations1(test1);
System.out.println("======");
printAllPermutations2(test1);
System.out.println("======");
String test2 = "acc";
printAllPermutations1(test2);
System.out.println("======");
printAllPermutations2(test2);
System.out.println("======");
}
}
printAllPermutations2(test1);
System.out.println("======");
String test2 = "acc";
printAllPermutations1(test2);
System.out.println("======");
printAllPermutations2(test2);
System.out.println("======");
}
}
|