一个机器人位于一个m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
分析：状态转移方程：,
维护一个二维数组，逐步计算；
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> res(m);
for(int i=0;i<m;i++)
res[i].resize(n);
for(int i=0;i<m;i++)
{
if(i<n)
res[i][i]=(i>0)?(res[i-1][i]+res[i][i-1]):1;
for(int j=i+1;j<n;j++)
{
res[i][j]=res[i][j-1]+((i>0)?res[i-1][j]:0);
}
for(int j=i+1;j<m&&i<n;j++)
{
res[j][i]=res[j-1][i]+((i>0)?res[j][i-1]:0);
}
}
return res[m-1][n-1];
}
};
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定n是一个正整数。
分析：状态转移方程：
class Solution {
public:
int climbStairs(int n) {
if(n==1)return 1;
if(n==2) return 2;
int pre=1;
int mid=2;
int next;
for(int i=3;i<=n;i++)
{
next=pre+mid;
pre=mid;
mid=next;
}
return next;
}
};
给你一个整数数组nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。
class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
ans.push_back({});
dfs(0,nums);
return ans;
}
void dfs(int st, vector<int>& nums) {
if (st == nums.size()) {
return;
}
for(int i=st;i<nums.size();i++)
{
temp.push_back(nums[i]);
ans.push_back(temp);
dfs(i+1,nums);
temp.pop_back();
}
}
};
