C++算法动态规划1

DP定义：

动态规划是分治思想的延申，通俗一点来说就是大事化小，小事化无的艺术。

在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。

动态规划具备了以下三个特点

1. 把原来的问题分解成了几个相似的子问题。
2. 所有的子问题都只需要解决一次。
3. 储存子问题的解。

动态规划的本质，是对问题状态的定义和状态转移方程的定义 (状态以及状态之间的递推关系)

动态规划问题一般从以下四个角度考虑：

1. 状态定义
2. 状态间的转移方程定义
3. 状态的初始化
4. 返回结果

状态定义的要求：定义的状态一定要形成递推关系。

一句话概括：三特点四要素两本质

适用场景：最大值 / 最小值，可不可行，是不是，方案个数

第 1 题 Fibonacci

• 难度：Easy
• 备注：斐波那契数列，出自《剑指 offer》
• 题目描述

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。

n<=39

递归实现

#include <bits/stdc++.h>
using namespace std;
int Fibonacci(int n) {if(n==0){return 0;}if(n==1 || n==2) {return 1;}return Fibonacci(n-1)+Fibonacci(n-2);
}
int main() {int n;cin>>n;cout<<Fibonacci(n);return 0;
}

动态规划实现

状态：斐波那契数列的某一项的值
状态定义 F (i)：斐波那契数列的第 i 项的值 -----> 把问题抽象出来
状态转移方程：
F (i) = F (i - 1) + F (i - 2)
状态初始化：
F (0) = 0, F (1) = 1 F (2) = 1
返回值：
斐波那契数列第 n 项值
F (n)

#include <bits/stdc++.h>
using namespace std;
int Fibonacci(int n) {if(n==0){return 0;}if(n==1 || n==2) {return 1;}//保存中间状态的结果 /*int * F=new int[n+1];//状态初始化F[0]=0;F[1]=1;//状态转移方程// F[i]= F[i-1]+F[i-2]for(int i=2;i<=n;++i){F[i]=F[i-1]+F[i-2];}  //返回结果 return F[n];*/int f0=0,f1=1,fn;for(int i=2;i<=n;++i){fn=f0+f1;//状态更新 f0=f1;f1=fn;} return fn;}
int main() {int n;cin>>n;cout<<Fibonacci(n);return 0;
}

第 2 题 变态青蛙跳台阶 (Climbing Stairs)

• 难度：Easy
• 备注：需要 C 基础，排列，出自《剑指 offer》
• 题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级…… 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

int jumpFloorII(int number)

来源：牛客 - 剑指 offer

#include <bits/stdc++.h>
using namespace std;
int jumpFloorII(int n){if(n<=0){return 0;}if(n==1){return 1;}int f=1;for(int i=2;i<=n;++i){f*=2;} return f;
}
int main() {int n;cin>>n;cout<<jumpFloorII(n);return 0;
}

问题变种

 

第 3 题 最大连续子数组和 (Maximum Subarray)

• 难度：Easy
• 备注：出自《剑指 offer》
• 题目描述

HZ 偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后，他又发话了：在古老的一维模式识别中，常常需要计算连续子向量的最大和，当向量全为正数的时候，问题很好解决。但是，如果向量中包含负数，是否应该包含某个负数，并期望旁边的正数会弥补它呢？例如：{6,-3,-2,7,-15,1,2,2}，连续子向量的最大和为 8（从第 0 个开始，到第 3 个为止）。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是 1)

int FindGreatestSumOfSubArray(vector<int> array)

 

#include <bits/stdc++.h>
using namespace std;
int FindGreatestSumOfSubArray(vector<int> array) {int len=array.size();int * ret=new int[len];//初始化ret[0]= array[0];for(int i=1; i<len; ++i) {//转移方程F[i]=max(F[i-1]+array[i],array[i])ret[i]=max(ret[i-1]+array[i],array[i]);}//返回max(F[i])int maxRet=ret[0];for(int i=1; i<len; ++i) {maxRet=max(maxRet,ret[i]);}return maxRet;
}
int main() {vector<int> a={6,-3,-2,7,-15,1,2,2};cout<<FindGreatestSumOfSubArray(a);return 0;
}