力扣62、482（2021/10/4每日一题）

• 题目一
• • 思路
  • • 为何用DP
    • 定状态
    • 初始化
    • 找转移
    • 找答案
  • 代码
• 题目二
• • 思路
  • • 正向模拟
    • 逆向模拟
  • 代码
  • • 正向模拟
    • 逆向模拟

力扣:62

我们注意到，就那终点作为例子，终点只能是由它上面和左面的点移动而来，所以路径数等于二者路径数目之和，这样的话，我们就明确的找到了小问题转换到大问题的过程，所以用DP。

只需要表示当前位置，所以用i,j表示位置即可

初始的时候就站在(1,1)处，所以只有到(1,1)处有一条路径

dp[i][j]只能从dp[i - 1][j] (如果不越界的话)和dp[i][j - 1] (如果不越界的话)转移而来，所以dp[i][j]等于二者之和，但要注意越界判断问题。

dp[m][n]为最后的位置即答案位置。

注：本体推荐用一维数组即滚动数组优化，本解法并未采用。

class Solution {
public:
	int dp[101][101] = {};//开足够大的空间，空间换时间
	int uniquePaths(int m, int n) {
		dp[1][1] = 1;//初始化
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (i - 1 > 0) {
					dp[i][j] += dp[i - 1][j];
				}
				if (j - 1 > 0) {
					dp[i][j] += dp[i][j - 1];
				}
			}
		}
		return dp[m][n];
	}
};

（所有代码均已在力扣上运行无误）

经测试，该代码运行情况是(经过多次测试所得最短时间)：

力扣:482

正向思路就是，完全按照题意走，唯一值得注意的是，因为是正向走，所以首段点的个数需要额外计算，根据题意，因为后面必须严格分段，所以首段长度就是(总长度%每段长度),后面直接模拟就行

正向模拟在首段问题上单独计算，那我们不妨换一个思路，我们先把后面规格统一的部分先搞了，最后剩下的一定<=k，然后对原字符串的处理，可以动态执行，然后每k个字符加一个’-’，最后注意一下有些特殊情况会导致最后多一个’-’，所以注意去除，结果和得到的串是反的。

class Solution {
public:
	string licenseKeyFormatting(string s, int k) {
		string item1 = "", ans = "";
		int n1 = s.size();
		for (int i = 0; i < n1; i++) {//处理原串
			if (s[i] == '-') {
				continue;
			}
			else if (s[i] >= 97 && s[i] <= 122) {
				item1 += (s[i] - 32);
			}
			else {
				item1 += s[i];
			}
		}
		int n2 = item1.size();
		int tmp1 = n2 % k;//计算首串长度
		int tmp2 = n2 / k;//段数
		int point = 0;//item1上取字符指针
		if (tmp1 != 0) {
			for (int i = 0; i < tmp1; i++) {
				ans += item1[point++];
			}
			if (tmp2 != 0) {//防止多'-'
				ans += '-';
			}
		}
		for (int i = 0; i < tmp2; i++) {//段数
			for (int j = 0; j < k; j++) {//每段中字符数
				ans += item1[point++];
			}
			if (i != tmp2 - 1) {
				ans += '-';//防止多'-'
			}
		}
		return ans;
	}
};

（所有代码均已在力扣上运行无误）

经测试，该代码运行情况是(经过多次测试所得最短时间)：

时间复杂度O(N^2)

class Solution {
public:
	string licenseKeyFormatting(string s, int k) {
		string ans = "";
		int n = s.size() - 1;
		int cnt = 0;
		for (int i = n; i >= 0; i--) {//对原串动态处理
			if (s[i] != '-') {
				cnt++;
				ans += toupper(s[i]);
				if (cnt%k == 0) {//这种方法就能分割出每k个长度的串
					ans += '-';
				}
			}
		}
		if (ans.size() > 0 && ans.back() == '-') {//注意检查特别情况
			ans.pop_back();
		}
		reverse(ans.begin(), ans.end());//倒置
		return ans;
	}
};

（所有代码均已在力扣上运行无误）

经测试，该代码运行情况是(经过多次测试所得最短时间)：