主持人做的化妆品网站,网站空间虚拟主机,wordpress no follow,黑龙江省营商环境建设监督局网站一、动态规划简介
动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ;
动态规划 , 没有具体的步骤 , 只有一个核心思想 ; 动态规划 的 核心思想 是 由大化小 , 大规模问题 使用 小规模问题 计算结果 解决 , 类似于 分治算法 ;
二、…一、动态规划简介
动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ;
动态规划 , 没有具体的步骤 , 只有一个核心思想 ; 动态规划 的 核心思想 是 由大化小 , 大规模问题 使用 小规模问题 计算结果 解决 , 类似于 分治算法 ;
二、动态规划解题步骤 三、例题 例题1 通过分析最近的一步来划分问题
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n1);for(int i 2; in; i){dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n];}
};例题2 分析过程 看最近一步操作dp[i] 与s[i]和s[i-1] 的解码关系有关 1.如果s[i]单独解码在1~9就可以解码但是题目问的是解码方法的总数在之前的所有解码类型后面加一个相同的字母解码方法并不会变化等于dp[i-1] 上一个dp的解码总数 解码总类变了而已失败就为0。 2.如果s[i]与s[i-1]解码在10~26内解码成功但是解码方法总数不会变化等于dp[i-2] 上两个dp的解码总数失败就为0. 所以dp[i] dp[i-1] dp[i2];
但是并不能直接带入需要依次判断后加入因为一旦单独解码或者一起解码失败的话就直接归0了。
class Solution {
public:int numDecodings(string s) {int n s.size();vectorint dp(n);//创建dp表dp[0] (s[0] ! 0);//初始化dp[0],dp[1]if(n 1) return dp[0];//边界情况int ret (s[0]-0)*10 (s[1] - 0);if(ret 10 ret 26) dp[1];if(s[1] ! 0 s[0] ! 0) dp[1];//填表for(int i 2; in; i){if(s[i] !0) dp[i] dp[i-1];//需要依次判断加入int t (s[i-1]-0)*10 s[i] - 0;if(t 10 t 26) dp[i] dp[i-2];}return dp[n-1];}
};
