64 最小路径和
给定一个包含非负整数的 m x n
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
解题思路:动态规划题步骤
dp[i][j]表示到i行j列最小路径和
1、初始化,dp[i][j]=grid[i-1][j-1]
只有一条路径的,即图形左边缘和上边缘,初始化。
dp[i][1]+=grid[j][0]
dp[1][i]+=grid[0][j]
3、确定状态转移方程
dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j]
int min(int a,int b){if(a>b)return b;else return a;
}
int minPathSum(int** grid, int gridSize, int* gridColSize) {//m为行,n为列int m=gridSize,n=gridColSize[0];if(m==0||n==0)return 0;int dp[205][205]={};//初始化for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=grid[i-1][j-1];}}for(int i=2;i<=m;i++){for(int j=0;j<i-1;j++){dp[i][1]+=grid[j][0];}}for(int i=2;i<=n;i++){for(int j=0;j<i-1;j++){dp[1][i]+=grid[0][j];}}//确定状态转移方程for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j];}}return dp[m][n];
}
139 单词拆分
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s
则返回 true
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
解题思路:动态规划
dp[i]=1表示前i个来自字典,Size[i]为字典中第i个单词的长度
1、初始化 dp[0]=1,其他为0
2、确定状态转移方程
i从1开始,那么k=i-1+Size[j]
dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0)
strcmp与strncmp都是用来比较字符串的,区别在于能否比较指定长度字符串,故要多传一个长度参数。头文件为<string.h>
——举个例子 leetcode 字典为leet code
Size[0]=4,Size[1]=4
i=1,j=0,k=4,dp[4]=dp[0]&&strncmp(s,wordDict[0],Size[0]==0)=1
i=2,j=0,k=5,dp[5]=dp[1]&&strncmp(s+1,wordDict[0],Size[0]==0)=0
……
i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[0],Size[0]==0)=0
i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[1],Size[1]==0)=1
所以dp[8]=1=true
思考:如果字典中的单词不能重复使用,该怎么做
可以设个标记flag数组,如果字典第i个单词用过,即dp[k]=1时,标记flag[j]为1。
j循环中,当flag[j]==0时才使用下面的步骤
bool wordBreak(char * s, char ** wordDict, int wordDictSize){int len=strlen(s),i,j;if(wordDictSize==0)return 0;int Size[wordDictSize]={};for(i=0;i<wordDictSize;i++)Size[i]=strlen(wordDict[i]);//dp[i]=1表示前i个来自字典int dp[len+1];dp[0]=1;for(i=1;i<=len;i++)dp[i]=0;for(i=1;i<=len;i++){for(j=0;j<wordDictSize;j++){int k=i-1+Size[j];if(k>len)continue;dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0);}}return dp[len];
}