动态规划相关算法1
- 斐波那契数列，爬楼梯：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法
f(n)=f(n-1)+f(n-2)
public int floorMethod(int n){
if(n==1){
return 1;
}
if(n==2){
return 2;
}
return floorMethod(n-1)+floorMethod(n-2);
}
- 抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量；如果是环形街区呢
-你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
maxMoney[i]表示到第i个元素的最大抢劫量。
递推公式：f(i)=max(f(i-1), f(i-2)+a[i))
public int robMaxMoney(int[] a) {
int[] maxMoney = new int[a.length];
if (a.length == 0) {
return 0;
}
if (a.length == 1) {
return a[0];
}
if (a.length == 2) {
return Math.max(a[0], a[1]);
}
maxMoney[0] = a[0];
maxMoney[1] = Math.max(a[0], a[1]);
for (int i = 2; i < a.length; i++) {
maxMoney[i] = Math.max(maxMoney[i - 1], maxMoney[i - 2] + a[i]);
}
return maxMoney[a.length - 1];
}
-Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.环形街区。
思路：第一个和最后一个不能同时抢。分两种情况，
第一种：不抢第一个
第二种：不抢最后一个
两者中的最大即为全局最大
public int robWithCycle(int[] a){
int max1=robMaxMoney(a,0,a.length-2);
int max2=robMaxMoney(a,1,a.length-1);
return Math.max(max1, max2);
}
/**
* @param a
* @param i
* @param length
* @return
*<p>Description: </p>
*/
private int robMaxMoney(int[] a, int start, int end) {
int length = end - start + 1;
if (length <= 0) {
return 0;
}
if (length == 1) {
return a[start];
}
if (a.length == 2) {
return Math.max(a[start], a[end]);
}
int maxMoney[] = new int[length];
maxMoney[0] = a[start];
maxMoney[1] = Math.max(a[start], a[end]);
for (int i = 2; i <= end - start; i++) {
maxMoney[i] = Math.max(maxMoney[i - 1], maxMoney[i - 2]
+ a[start + i]);
}
return maxMoney[length - 1];
}
-树形街区偷到问题详见（https://www.jianshu.com/p/e774e331aee0）
- 母牛生产：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量
f(n)=f(n-1)+f(n-3)
public int cowNum(int n){
if(n==1 || n==2 ||n==3){
return n;
}
return cowNum(n-1)+cowNum(n-3);
}
- 信件错排：有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量
问题解决
首先考虑几种简单的情况：
- 原序列长度为1
序列中只有一个元素，位置也只有一个，这个元素不可能放在别的位置上，因此原序列长度为1时该为题的解是0。 - 原序列长度为2
设原序列为{a,b}，则全错位排列只需将两个元素对调位置{b,a}，同时也只有这一种可能，因此原序列长度为2时该问题的解是1。 - 原序列长度为3
设原序列为{a,b,c}，则其全错位排列有：{b,c,a},{c,a,b}，解是2。 - 原序列长度为4
设原序列为{a,b,c,d}，则其全错位排列有：{d,c,a,b},{b,d,a,c},{b,c,d,a},{d,a,b,c},{c,d,b,a},{c,a,d,b},{d,c,b,a},{c,d,a,b},{b,a,d,c}，解是9。
解题思路：
设长度为n的序列的全错位排列一共有f(n)种，假设我们已经解决了f(1)到f(n-1)，那么当序列新增了一个元素an，显然全错位排列中该元素不能放在第n个位置上，假设该元素在从1到n-1的第i个位置，那么在新序列中第n个位置上的元素可能有两种情况：
第n个位置上的元素为ai
因为an和ai都不在原位置上，因此只需剩余的元素都是全错位排列，新序列就构成了全错位排列。那么除去ai和an还剩下n-2个元素，则这n-2个元素一共有f(n-2)种全错位排列，因为i的选择共有n-1种，因此该情况下一共有(n-1)f(n-2)种全错位排列。
第n个位置上的元素不为ai
该种情况相当于，前n-1个元素做好了全错位排列，an与其中任意元素交换位置，新生成的序列也是一个全错位排列。这种情况下i的选择共有n-1种，n-1的元素的全错位排列共有f(n-1)种，因此该情况下一共有(n-1)f(n-1)种全错位排列。
综合以上两种情况，f(n)=(n-1)f(n-2)+(n-1)*f(n-1)=(n-1)[f(n-2)+f(n-1)]
例如：原序列为｛a,b,c,d,e｝，则新序列{b,c,d,e,a}为其一个全错位排列，新序列中每一个元素都不在原来的位置上。
public int errorNum(int n){
if(n==1){
return 0;
}
if(n==2){
return 1;
}
return (n-1)*(errorNum(n-1)+errorNum(n-2));
}
趴楼梯的最小代价
//On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
//
//Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
//
//Example 1:
//Input: cost = [10, 15, 20]
//Output: 15
//Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
//Example 2:
//Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
//Output: 6
//Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
//Note:
//cost will have a length in the range [2, 1000].
//Every cost[i] will be an integer in the range [0, 999].
public int minCostOfClimb(int[] a){
if(a.length<=0){
return 0;
}
if(a.length==1){
return a[0];
}
if(a.length==2){
return Math.min(a[0], a[1]);
}
int[] dp=new int[a.length];
dp[0]=a[0];
dp[1]=a[1];
for(int i=2;i<dp.length;i++){
dp[i]=Math.min(dp[i-1]+a[i], dp[i-2]+a[i]);
}
return Math.min(dp[dp.length-1],dp[dp.length-2]);
}
上述问题，求代价最小时的路径？
解法1：求得最小代价是走一步还是走两步走到的。这个解法的问题时，不是特别的清楚的说明是从第一个台阶开始走的还是第二个。
public List getSeps(int[] a){
List<Integer> list=new ArrayList();
if(a.length<=0){
return list;
}
if(a.length==1){
list.add(2);// go two steps
return list;
}
if(a.length==2){
if(a[0]<=a[1]){
list.add(2);
}
else{
list.add(1);
}
return list;
}
int[] dp=new int[a.length];
dp[0]=a[0];
dp[1]=a[1];
for(int i=2;i<dp.length;i++){
dp[i]=Math.min(dp[i-1]+a[i], dp[i-2]+a[i]);
}
Stack<Integer> stack=new Stack<>();
for(int i=a.length-1;i>0;){
if(dp[i]>=dp[i-1]){
stack.push(2);
i=i-2;
}
else{
stack.push(1);
i=i-1;
}
}
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
如果输入是 int[] t5={1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
以上的结果是：
[2, 2, 2, 1, 2, 1]
解法2：返回台阶的索引
public List getSepsIndex(int[] a){
List<Integer> list=new ArrayList();
if(a.length<=0){
return list;
}
if(a.length==1){
list.add(0);// go two steps
return list;
}
if(a.length==2){
if(a[0]<=a[1]){
list.add(0);
}
else{
list.add(1);
}
return list;
}
int[] dp=new int[a.length];
dp[0]=a[0];
dp[1]=a[1];
for(int i=2;i<dp.length;i++){
dp[i]=Math.min(dp[i-1]+a[i], dp[i-2]+a[i]);
}
Stack<Integer> stack=new Stack<>();
for(int i=a.length-1;i>0;){
if(dp[i]>=dp[i-1]){
stack.push(i-1);
i=i-2;
}
else{
stack.push(i);
i=i-1;
}
}
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
如果输入是 int[] t5={1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
以上解法的输出：
[0, 2, 4, 6, 7, 9]
-最长公共子串
最长回文子串
数字的最大连续子数组之和
https://blog.csdn.net/chiyiyan1586/article/details/78858934
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法
f(n)=f(1)+f(2)+...+f(n-1)
f(n-1)=f(1)+f(2)+...+f(n-2）
推导出f(n)=2*f(n-1)
public int floorNum(int n){
if(n==0|| n==1){
return n;
}
int pre=1;
int result=0;
for(int i=2;i<=n;i++){
result=2*pre;
pre=result;
}
return result;
}
```
或者用递归
```java
public int floorNumRecusive(int n){
if(n==0|| n==1){
return n;
}
return 2*floorNumRecusive(n-1);
}
