不同路径
//机器人不同的路径进入到指定的地点
public static int uniquepath(int m, int n) {if (m <= 0 || n <= 0){return 0;}int[][] dp = new int[m][n];//初始化//如果只有i,j中有一个为0,那么机器人行走的方向只能有一种方式for (int i = 0; i < m; i++){dp[i][0] = 1;}for (itn i = 0; i < n; i++) {dp[0][i] = 1; }//推导出dp[m-1][n-1],因为定义dp[i][j]就是表示的是在[i][j]点 //不同的路径的数目 for (itn i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }}return dp[m - 1][n - 1]; }
不同路径||
![在这里插入图片描述](https://img-blog.csdnimg.cn/55c59dbc1da64e20aed014ff76118002.png)
方法一:
大佬讲解
class Solution {
public:/*** 1. 确定dp数组下标含义 dp[i][j] 从(0,0)到(i,j)可能的路径种类;* 2. 递推公式 dp[i][j] = dp[i-1][j] + dp[i][j-1] 但是需要加限制条件就是没有障碍物的时候* if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];* 3. 初始化 当obstacleGrid[i][j] == 0时,dp[i][0]=1 dp[0][i]=1 初始化横竖就可;* 4. 遍历顺序 一行一行遍历;* 5. 推导结果;*/int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {/* 计算数组大小 */int m = obstacleGrid.size();int n = obstacleGrid[0].size();/* 定义dp数组 */vector<vector<int>> dp(m,vector<int>(n,0));/* 初始化dp数组 */for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++)dp[i][0] = 1; for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++) dp[0][i] = 1; /* 一行一行遍历 */ for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { /* 去除障碍物 */ if(obstacleGrid[i][j] == 1) continue; dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}return dp[m-1][n-1]; }
};
方法二
多加一行和一列的虚拟节点,防止出现越界的情况,
把它们初始化成0,但是要保证第一个节点初始化成1.
dp[0][1] = 1;
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));dp[0][1] = 1;for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {if(obstacleGrid[i - 1][j - 1] == 1) continue;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];}
第N个泰波那契数
递归写法
1。先确定函数的一定是什么dp[ i ] 表示:第 i 个泰波那契数
2。题目中的关系代数是 dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3。边界是T(0)=0,T(1)=1,T(2)=1T(0)=0, T(1)=1,
4。初始化为dp[ 0 ] = 0,dp[ 1 ] = 1,dp[ 2 ] = 1
class Solution {
public:int tribonacci(int n) {vector<int> dp(n + 1);if (n == 0) {return 0; }if (n <= 2) {return 1; }dp[0] = 0, dp[1] = 1, dp[2] = 1; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; }return dp[n]; }
};
滚动数组
class Solution {
public:int tribonacci(int n) {if (n == 0) {return 0;}if (n <= 2) { return 1; }int p = 0, q = 0, r = 1, s = 1; for (int i = 3; i <= n; ++i) { p = q; q = r; r = s; s = p + q + r; }return s; }
};
三步问题
这就是老油条的步骤了,
先确定自己定义的函数,然后找出关系式,然后确定初始值
递归操作
class Solution {
public: int waysToStep(int n) { vector<in#t> dp(n + 1); const int MOD = 1e9 + 7; //边界问题 if (n == 1 || n == 2) return n; if (n == 3) return 4; //初始化定义 dp[1] = 1, dp[2] = 2, dp[3] = 4; for (int i = 4; i <= n; i++) { dp[i] = ((dp[i - 3] + dp[i - 2]) % MOD + dp[i - 1]) % MOD; }return dp[n]; }
};
滚动数组
class Solution {
public: int waysToStep(int n) { int a=1,b=2,c=4,i; for(i=2;i<=n;i++){ long long t=(a+b)%1000000007; t=(t+c)%1000000007; a=b; b=c; c=t; }return a; }
};
使用最小画法爬楼梯
题目要求的是到达第n级台阶楼层顶部的最小花费,可以用动态规划来解,下面一步一步来讲怎样确定状态空间、怎样给出状态转移方程。
递归
-
大佬讲解
-
最近的一步有两种情况,
-
从 dp[ i - 1 ] 走一步过来,支付cost[ i - 1 ] 的费用; 1. 从 dp[ i - 1 ] 走一步过来,支付cost[ i - 1 ] 的费用;
-
从 dp[ i - 2 ] 走两步过来,支付cost[ i - 2 ] 的费用。
而 dp[ i ] 就是到达 i 位置的最小花费,
那我们就能得出状态转移方程:
dp [ i ] = min( dp[ i - 1 ] + cost[ i - 1 ],dp[ i - 2 ] + cost[ i - 2 ] )
class Solution {
public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); // 创建dp表,这样初始化默认填充的是 0 vector<int> dp(n + 1); for (int i = 2; i <= n; i++) { dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); }return dp[n]; }
};
解码方法
方法一
动态规划的使用:
1。确立dp 数组的定义,代表的是 dp[i] 位置代表的是第i个位置时候解码方法的总数。
2。找关系代数=
-
s[ i ] 单独解码,如果是单独解码,当 s[ i ] 的值是 1~9 的时候可以自己解码,
自己解码的方案数就是 dp[ i - 1 ],如果 s[ i ] 的值是 0,那方案数就是0,整体解码失败, -
s[ i ] 和 s[ i - 1 ] 一起解码,当 s[ i - 1 ] * 10 + s[ i ] 的值是 10~26 的时候就可以解码,
而解码数就是 dp[ i - 2 ],如果解码失败,不在这个区间内,那方案数就也是0。
3。初始化dp数组,
初始化 dp[ 0 ] 和 dp[ 1 ] 位置,
dp[ 0 ] 位置,如果s[ 0 ] 解码成功就是1,不成功就是0
dp[ 1 ] 位置,如果 dp[ 1 ] 能自己解码,就 + 1,如果能跟 dp[ 0 ] 一起解码,就再 + 1,
如果dp[ 1 ] 两种情况都不能解码,就是0。(所以可能是0, 1, 2)
class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(size);dp[0] = s[0] != '0';if (size == 1) return dp[0];if (s[0] != '0' && s[1] != '0') dp[1]++;int t = (s[0] - '0') * 10 + (s[1] - '0');if (t >= 10 && t <= 26) dp[1]++;for (int i = 2; i < size; i++) {if (s[i] != '0') dp[i] += dp[i - 1]; t = (s[i - 1] - '0') * 10 + (s[i] - '0');if (t >= 10 && t <= 26) dp[i] += dp[i - 2]; //一起解码}return dp[n - 1];}
};
方法二:(大佬讲解)
class Solution {
public:int numDecodings(string s) {if (s[0] == '0') return 0;int n = s.size();vector<int> dp(n + 1, 1);//dp[0]表示s[-1]的状态, dp[1] 表示 s[0]的状态//dp[i] 表示 s[i-1]的状态for (int i = 2; i <= n; i++) {if (s[i - 1] == '0') {if (s[i - 2] == '1' || s[i - 2] == '2')//唯一译码,不增加情况dp[i] = dp[i - 2]; else//这里要好好理解一下,比如给定340, 输出可行的编码数为0, 因为0和40都无法转换 return 0; }else if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] >= '1' && s[i - 1] <= '6')dp[i] = dp[i - 1] + dp[i - 2]; else//当上述条件都不满足,维持上一个状态 dp[i] = dp[i - 1]; }//for(auto c:dp) cout << c << ","; return dp[n];//返回dp[n] 即最后 s[n-1] 的状态 }
};