php网站访问量代码,网上商城网站开发,谷歌官网下载,沈阳网站建设哪里的公司比较好一、动态规划的算法原理 这是本人动态规划的第一篇文章#xff0c;所以先阐述一下动态规划的算法原理以及做题步骤。动态规划本人的理解就是通过题目所给的条件正确地填满dp表#xff08;一段数组#xff09;。首先要先确定好dp表每个位置的值所代表的含义是什么#xff0c…一、动态规划的算法原理 这是本人动态规划的第一篇文章所以先阐述一下动态规划的算法原理以及做题步骤。动态规划本人的理解就是通过题目所给的条件正确地填满dp表一段数组。首先要先确定好dp表每个位置的值所代表的含义是什么然后通过题目条件以及经验推出状态转移方程第三个就是初始化确定填表顺序以及保证填表不越界最后输出题目所需的结果大致就是这个思路。
二、斐波那契数列模型例题分析
1137. 第 N 个泰波那契数 - 力扣LeetCode 本题的思路较为简单状态转移方程已经给出直接上代码
class Solution {
public:int tribonacci(int n) {vectorint v1(n1);//初始化if(n 1)return 1;else if(n 2)return 1;else if(n 0)return 0;v1[0] 0;v1[1] 1;v1[2] 1;for(int i 3; i n; i){v1[i] v1[i-1] v1[i-2] v1[i-3];}return v1[n];}
}; 面试题 08.01. 三步问题 - 力扣LeetCode 解析 假设小孩此时正处于某一台阶上那他是如何到达这一台阶的呢是不是他有可能是从该台阶的前一个台阶跳上来的也可能是从该台阶的前两个台阶跳上来的也可能是从该台阶的前三个台阶跳上来的所以小孩到某一台阶就有三种可能情况也即dp表中某个位置的值就是这个位置前三个位置的值相加从而确定出了状态转移方程。
class Solution {
public:int waysToStep(int n) {//创建dp表vectorint v1(n1);if(n 1)return 1;if(n 2)return 2;if(n 3)return 4;//初始化v1[1] 1;v1[2] 2; v1[3] 4;for(int i 4; i n; i){//确定状态转移方程这里需要注意加数的和可能会越界根据题目要求要对1000000007取模v1[i] ((v1[i-1] v1[i-2]) % 1000000007 v1[i-3])%1000000007;} return v1[n];}
}; 746. 使用最小花费爬楼梯 - 力扣LeetCode 解析 要确定每一级楼梯最低花费通过比较前两级楼梯确定应该加的值从而确定状态转移方程。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int length cost.size();//dp表vectorint MinCost(length);//初始化for(int i 0; icost.size(); i){MinCost[i] cost[i];}//状态转移方程for(int i 2; ilength; i){if(MinCost[i-1] MinCost[i-2]){MinCost[i] MinCost[i-1];}else{MinCost[i] MinCost[i-2];}}if(MinCost[cost.size() - 1] MinCost[cost.size() - 2]){return MinCost[cost.size() - 1];}else{return MinCost[cost.size() - 2];}}
}; 91. 解码方法 - 力扣LeetCode 解析 选定一个位置作为结尾如果这个位置的值不为零就看其能否与前一个位置的值组成合法编码如果能这个位置的值就是它的前一个位置加上它的前前一个位置的值如果不能这个位置的值就是它的前一个位置的值如果这个位置的值为零就看其能否与前一个位置的值组成合法编码如果能这个位置的值就是它的前前一个位置的值。
class Solution {
public:int numDecodings(string s) {int len s.length();int arr[len];const char* str;str s.c_str();for(int i 0; ilen; i){arr[i] str[i] - 48;}//处理特殊情况if(arr[0] 0){return 0;}else if(len 1 arr[0] ! 0){return 1;}for(int i 1; ilen; i){//例30if(arr[i] 0 (arr[i-1] 2)){return 0;}//例1001else if(i1 len arr[i] 0 arr[i1] 0){return 0;}}for(int i 0; ilen; i){cout arr[i] ;}//dp表vectorint vect(len1);//初始化vect[0] 1;vect[1] 1;//状态转移方程for(int i 2; i vect.size(); i){if(arr[i-1] ! 0){if(arr[i-2] ! 0 ((arr[i-1] arr[i-2]*10) 26)){vect[i] vect[i-1] vect[i-2];}else{vect[i] vect[i-1];}}else{vect[i] vect[i-2];}}return vect[len];}
};
